[图论记录]AT3883 [ARC090C] Avoiding Collision
command_block
2021-05-11 15:11:49
**题意** ： 给出一张含有 $n$ 个点 $m$ 条带权边的无向图。
有两人分别在 $S,T$ ，他们要前往对方的位置。
求两人都走最短路且不相遇（点上和边上相遇都不行）的方案数。答案对 $10^9+7$ 取模。
$n\leq 10^5,m\leq 2\times 10^5$ ，时限$\texttt{2s}$。
------------
建立从 $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$
- 在边 $(u,v,w)$ 上相遇（不包括端点）（注意 $u,v$ 可以交换）
条件 ： $d_S[u]+d_T[v]+w=dis$ 且 $\big(d_S[u],d_S[u]+w\big)∩\big(d_S[u],d_S[u]+w\big)\neq \varnothing$。
方案数 ： $f_S[u]^2f_T[v]^2$
复杂度 $O(n\log n)$。
```cpp
#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;
}
```