AtCoder ARC 090 E / AtCoder 3883: Avoiding Collision

题目传送门：ARC090E。

题意简述：

给定一张有 \(N\) 个点 \(M\) 条边的无向图。每条边有相应的边权，边权是正整数。

小 A 要从结点 \(S\) 走到结点 \(T\) ，而小 B 则相反，他要从结点 \(T\) 走到结点 \(S\) 。

小 A 和小 B 走一条边需要的时间都是这条边的边权，不论方向。

问有多少种走法，使得他们俩都走了最短路，但是他们不会相遇，这里相遇指的是在点上或者在边上相遇。

答案对 \(10^9+7\) 取模。

题解：

用 Dijkstra 算法求出以结点 \(S\) 和结点 \(T\) 出发到每个点的最短路和最短路条数。

把从结点 \(S\) 到结点 \(i\) 的最短路记作 \(d1_i\) ，最短路条数对 \(10^9+7\) 取模的结果记作 \(g1_i\)。

把从结点 \(T\) 到结点 \(i\) 的最短路记作 \(d2_i\) ，最短路条数对 \(10^9+7\) 取模的结果记作 \(g2_i\)。

把从结点 \(S\) 到结点 \(T\) 的最短路记作 \(Dist\) 。

考虑用容斥的方法计算答案。答案等于总方案数减去相遇的方案数。总方案数为 \(g1_T^2\) 。

因为走的都是最短路，而且边权是正的，不难证明两人只会相遇一次。

所以只要统计在每个点或者每条边经过的方案数即可。

考虑经过结点 \(i\) 的方案数：
前提是 \(d1_i+d2_i=Dist\) 且 \(d1_i=d2_i\) ，方案数为 \(g1_i^2g2_i^2\) 。

考虑经过边 \(i\overset{d}{\Longleftrightarrow}j\) （其中小 A 从结点 \(i\) 走向结点 \(j\) ）的方案数：
前提是 \(d1_i+d+d2_i=Dist\) 且 \(d1_i+d>d2_j\) 且 \(d1_i<d+d2_j\) ，方案数为 \(g1_i^2g2_j^2\) 。

 #include<bits/stdc++.h>

 #define F(i,a,b) for(int i=(a);i<=(b);++i)

 #define eF(i,u) for(int i=h[u];i;i=nxt[i])

 #define Mod 1000000007

 using namespace std;

 typedef long long ll;

 typedef pair<ll,int> pli;

 int n,m,S,T;

 ll Ans;

 int U[],V[],D[];

 int h[],nxt[],to[],w[],tot;

 void ins(int x,int y,int z){nxt[++tot]=h[x];to[tot]=y;w[tot]=z;h[x]=tot;}

 ll d1[],d2[],g1[],g2[];bool v1[],v2[];

 priority_queue<pli,vector<pli>,greater<pli> > pq;

 void Dij(ll*d,ll*g,bool*v,int s){

     d[s]=0ll;

     pq.push(pli(0ll,s));

     g[s]=;

     while(!pq.empty()){

         pli P=pq.top(); pq.pop();

         int u=P.second; ll du=P.first;

         if(v[u]||d[u]<du) continue;

         v[u]=;

         eF(i,u){

             if(d[to[i]]==du+w[i])

                 g[to[i]]=(g[to[i]]+g[u])%Mod;

             if(d[to[i]]>du+w[i])

                 g[to[i]]=g[u],

                 d[to[i]]=du+w[i], pq.push(pli(d[to[i]],to[i]));

         }

     }

 }

 int main(){

     int x,y,z;

     scanf("%d%d",&n,&m);

     scanf("%d%d",&S,&T);

     F(i,,m) scanf("%d%d%d",&x,&y,&z), ins(x,y,z), ins(y,x,z), U[i]=x, V[i]=y, D[i]=z;

     memset(d1,0x3f,sizeof d1);

     Dij(d1,g1,v1,S);

     memset(d2,0x3f,sizeof d2);

     Dij(d2,g2,v2,T);

     ll Dist=d1[T];

     Ans=g1[T]*g1[T]%Mod;

     F(i,,n){

         if(d1[i]+d2[i]==Dist&&d1[i]==d2[i])

             Ans=(Ans-g1[i]*g1[i]%Mod*g2[i]%Mod*g2[i]%Mod)%Mod;

     }

     int u,v,d;

     F(i,,m){

         u=U[i], v=V[i], d=D[i];

         if(d1[u]+d+d2[v]==Dist && d1[u]+d>d2[v] && d2[v]+d>d1[u]){

             Ans=(Ans-g1[u]*g2[v]%Mod*g1[u]%Mod*g2[v]%Mod)%Mod;

         }

         u=V[i], v=U[i], d=D[i];

         if(d1[u]+d+d2[v]==Dist && d1[u]+d>d2[v] && d2[v]+d>d1[u]){

             Ans=(Ans-g1[u]*g2[v]%Mod*g1[u]%Mod*g2[v]%Mod)%Mod;

         }

     }

     printf("%lld",(Ans%Mod+Mod)%Mod);

     return ;

 }

巴特西

AtCoder ARC 090 E / AtCoder 3883: Avoiding Collision

最新文章

热门文章