[图论记录]AT3883 [ARC090C] Avoiding Collision

· · 个人记录

题意 ： 给出一张含有 n 个点 m 条带权边的无向图。

有两人分别在 S,T ，他们要前往对方的位置。

求两人都走最短路且不相遇（点上和边上相遇都不行）的方案数。答案对 10^9+7 取模。

------------ 建立从 $S\rightarrow T,\ T\rightarrow S$ 的最短路 $\rm DAG$。 记 $f_S[u]$ 为 $u\leftrightarrow S$ 的最短路径数，$d_S[u]$ 为 $S\leftrightarrow u$ 的最短距离。 类似地定义 $f_T[u],d_T[u]$。 记 $dis=d_S[T]$ ，记 $S,T$ 之间的最短路长度。 若允许两人相遇，则方案数为两个 $\rm DAG$ 路径数的乘积。即 $f_S[T]^2$。 考虑容斥，减去不合法的方案。 不难发现，在走最短路的基础上，两人若相遇，只能相遇一次。 枚举在那个点或那条边上相遇 ： - 在点 $u$ 上相遇 条件 ： $d_S[u]+d_T[u]=dis$ 且 $d_S[u]=d_T[u]$。 方案数 ： $f_S[u]^2f_T[u]^2

复杂度 O(n\log n)。

#include<algorithm>
#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>
#define ll long long
#define Pr pair<ll,int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
#define MaxN 100500
using namespace std;
const int mod=1000000007;
vector<int> g[MaxN],l[MaxN];
priority_queue<Pr> q;
int n;
void dijk(int S,ll *dis,int *f)
{
  for (int i=1;i<=n;i++)dis[i]=1ll<<60;
  q.push(mp(dis[S]=0,S));f[S]=1;
  while(!q.empty()){
    Pr now=q.top();q.pop();
    if (-now.fir!=dis[now.sec])continue;
    int u=now.sec;
    for (int i=0,v;i<g[u].size();i++){
      if (dis[v=g[u][i]]>dis[u]+l[u][i])
        q.push(mp(-(dis[v]=dis[u]+l[u][i]),v));
      if (dis[v]+l[u][i]==dis[u])
        f[u]=(f[u]+f[v])%mod;
    } 
  }
}
ll ds[MaxN],dt[MaxN];int fs[MaxN],ft[MaxN];
int m,S,T;
int main()
{
  scanf("%d%d%d%d",&n,&m,&S,&T);
  for (int i=1,u,v,w;i<=m;i++){
    scanf("%d%d%d",&u,&v,&w);
    g[u].pb(v);l[u].pb(w);
    g[v].pb(u);l[v].pb(w);
  }dijk(S,ds,fs);dijk(T,dt,ft);
  int ans=1ll*fs[T]*fs[T]%mod;ll dis=ds[T];
  for (int u=1;u<=n;u++){ 
    if (dis==ds[u]+dt[u]&&ds[u]==dt[u])
      ans=(ans-1ll*fs[u]*fs[u]%mod*ft[u]%mod*ft[u])%mod;
    for (int i=0;i<g[u].size();i++){
      int v=g[u][i];
      if (ds[u]+dt[v]+l[u][i]==dis&&dt[v]<ds[u]+l[u][i]&&ds[u]<dt[v]+l[u][i])
        ans=(ans-1ll*fs[u]*fs[u]%mod*ft[v]%mod*ft[v])%mod;
    }
  }printf("%lld",(ans+mod)%mod);
  return 0;
}