AT3883 [ARC090C] Avoiding Collision

AT3883 [ARC090C] Avoiding Collision TJ

题意：

给定一个 $ N $ 个点 $ M $ 条边的无向图，每条边附加有正整数边权（时间），给出两个点 $ S $ 和 $ T $，询问分别从两个点出发，走最短路时不在同一时刻相遇的方案数，答案对 $ 10 ^ 9 + 7$ 取模。

吐槽：

考场上想出个半正解，得了50pts，旁边的老哥写了个rand，得了40pts，半正解险些被rand吊打……

思路：

首先因为涉及到最短路与方案数，优先往Dijkstra和组合数学上面想。SPFA已经死了

考场上的我很蒻，也很天真，想出来一种50pts神仙计数：

对于这两个点之间的最短路，计方案数有 $ cnt $ 个。

由于要求两条最短路不在同一时刻相交，所以一个走这条，另一个走另一条，大概率（这么玄学的做法我也敢打上去就奇怪了）不会相遇。

所以答案为 $ cnt \times (cnt-1)$。

这显然不对，但考试时的数据是真的水。。。

考虑正解。

乱搞一波可以发现，直接求方案数不好求，猜一波容斥。用总方案数减去相遇的方案数。

对于 $ S $ 和 $ T $ ，分别求出他们到每个节点的最短路与对应的方案数。记到点i的最短路分别为 $ dis_i $ 和 $ dit_i $，方案数分别为 $ cns_i $ 与 $ cnt_i $。

现在我们知道了总的方案数为： $ cns_t \times cnt_s $ ，考虑怎么求出相遇的方案数。

来一波分类讨论：

1. 在点上相遇：若在点i上相遇，则要求 $ dis_i = dit_i$ 且 $ dis_i + dit_i = dis_t $，方案数为： $ (cns_i \times cnt_i)^2 $，这个式子的意义为：在从两边到这个点的方案中，任选两个的方案数。
2. 在边上相遇：同理可得，若在边 $ ( u , v , d ) $ 上相遇，则要求： $ dis_u + dit_v + d = dis_t $ 并且 $ dis_u + d > dit_v $ 同时 $ dit_v +d > dis_u $（这个判断可能有冗余，但我没改，毕竟稳妥第一），此时的方案数为： $ cns_u \times cnt_v ) ^ 2 $ 。

那么在跑完最短路之后枚举判断一波即可。

时间复杂度在 $ O(m log n ) + O ( n ) + O ( m )$，即 $ O ( m log n ) $，非常的nice。

考虑一下正确性：由于边权为正，可以发现两人最多相遇一次不然你跑的什么最短路，因此只需要判断一次相遇的情况即可。

所以这道题就做完了。

代码实现：

不建议直接看代码，尝试自己写一下（毕竟是真的好写啊）。

大概需要邻接表存个图，结构体单独存下边，跑两个最短路，然后暴力组合计数。涉及到的东西真的不多又基础。

写完之后可以交一发信仰过题，实在是找不出问题再来看代码也不迟。

AC code：

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
namespace OI{
	template<class T> inline T Min(const T &x,const T &y){
		return x<y?x:y;
	}
	template<class T> inline T Max(const T x,const T y){
		return y<x?x:y;
	}
	template<class T> inline void Swap(T &x,T &y){
		T tmp=x;
		x=y,y=tmp;
	}
	const int MAXSIZE=1048576;
	char buf[MAXSIZE], *p1, *p2;
	#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++)
	template<class T=int> inline int read(){
		int x=0;bool f=1;char ch=gc();
		while('0'>ch||'9'<ch){if(ch=='-')f=0;ch=gc();}
		while('0'<=ch&&'9'>=ch)x=(x<<3)+(x<<1)+(ch^48),ch=gc();
		return f?x:-x;
	}
	template<class T> inline void write(T x){
		static int sta[128];
		int top=0;
		do{
			sta[top++]=x%10,x/=10;
		}
		while(x);
		while(top) putchar(sta[--top]^48);
	}
}//日常卡常
using namespace OI;
const int MAXN=100005,MAXM=MAXN<<1,M=1e9+7;
int n,m,s,t;
template<class T>struct node{
	int v;
	T d;
	friend bool operator<(const node &x,const node &y){
		return x.d>y.d;
	}
};
vector<node<int> > G[MAXN];//存图
template<class T>struct edge{//别问，问就是为了卡时间+少打一个结构体
	int u,v;
	T d;
};
edge<ll> e[MAXM];//存边
inline void spfa(const int &s,ll *dis,ll *cns,bool *vis){//这里传了数组的指针进去，就可以直接修改
	for(int i=1;i<=n;i++) dis[i]=0x7fffffffffffffff;
	priority_queue<node<ll> >S;
	cns[s]=1,dis[s]=0;
	S.push({s,0});
	while(!S.empty()){
		int u=S.top().v;
		S.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<(int)G[u].size();i++){
			int v=G[u][i].v,d=G[u][i].d; 
			if(dis[v]>dis[u]+d){
				dis[v]=dis[u]+d;
				S.push({v,dis[v]});
				cns[v]=cns[u];
			}
			else if(dis[v]==dis[u]+d) cns[v]=(cns[v]+cns[u])%M;
		}
	}
}//这个函数名……懂得都懂！
ll dis[MAXN];
ll dit[MAXN];
bool vis[MAXN];
bool vit[MAXN];
ll cns[MAXN];
ll cnt[MAXN];
template<class T>inline T two_pow(T x){
	return x*x%M;
}
inline ll calc_ans(){
	return two_pow(cns[t]);
}
inline ll cut(){//计算相遇的方案数
	ll ret=0;
	for(int k=1;k<=n;k++) if(dis[k]+dit[k]==dis[t]&&dis[k]==dit[k]) ret=(ret+two_pow(cnt[k]*cns[k]%M))%M;
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v;
		ll d=e[i].d;
		if(dis[u]+dit[v]+d==dis[t]&&dis[u]+d>dit[v]&&dit[v]+d>dis[u]) ret=(ret+two_pow(cns[u]*cnt[v]%M))%M;
		if(dis[v]+dit[u]+d==dit[s]&&dis[v]+d>dit[u]&&dit[u]+d>dis[v]) ret=(ret+two_pow(cns[v]*cnt[u]%M))%M;//注意方向不同是有影响的
	}
	return ret;
}
signed main(){
	n=read(),m=read(),s=read(),t=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),d=read();
		G[u].push_back({v,d}),G[v].push_back({u,d});
		e[i]={u,v,d};
	}
	spfa(s,dis,cns,vis);
	spfa(t,dit,cnt,vit);
	write(((calc_ans()-cut())%M+M)%M);//主函数简洁又快乐
	return 0;
}

大概就是这么个样子……