题解：CF1650G Counting Shortcuts

· · 题解

好题。

思路

转化一下题意：在有向图中求从 s 到 t 的最短路径数量与次短路径数量之和。

由于边权为 1，所以直接上 BFS。

设：任何长度为 D+1 的路径，其长度比最短路多 1。这意味着次短路恰好有一条边没有向终点靠近。所以，一条次短路可以被拆分为：

答案为最短路数量与次短路数量之和。

所以我们只要把两条路径求出来，问题就迎刃而解了。

设 dis1_i 与 cnt1_i 分别为从 s 到 i 的距离和路径数量。dis2_i 与 cnt2_i 分别为 i 到 s 的距离和路径数量。u 与 v 分别为当前点和下一个点。枚举每一条边，则：

记得给 ans 取模！

代码

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=2e5+10;
const int mod=1e9+7;
int T;
int n,m;
int u,v;
int s,t;
int dis1[N],dis2[N];
int cnt1[N],cnt2[N];
bitset<N> vis;
queue<int> q;
vector<int> g[N];
vector<pii> e;
void bfs(int s,int dis[],int cnt[]){
    for(int i=1;i<=n;++i){
        dis[i]=-1;
        cnt[i]=0;
    }
    dis[s]=0;
    cnt[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto v:g[u]){
            if(dis[v]==-1){
                dis[v]=dis[u]+1;
                cnt[v]=cnt[u];
                q.push(v);
            }
            else if(dis[v]==dis[u]+1){
                cnt[v]=(cnt[v]+cnt[u])%mod;
            }
        }
    }
    return;
}
void solve(){
    vis.reset();
    e.clear();
    cin>>n>>m;
    cin>>s>>t;
    for(int i=1;i<=n;++i){
        g[i].clear();
        dis1[i]=dis2[i]=cnt1[i]=cnt2[i]=0;
    }
    for(int i=1;i<=m;++i){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);  
        e.emplace_back(u,v);
    }
    bfs(s,dis1,cnt1);
    bfs(t,dis2,cnt2);
    int ans=cnt1[t];
    for(auto T:e){
        int u=T.first,v=T.second;
        if(dis1[u]==dis1[v]){
            if(dis1[v]+dis2[v]==dis1[t])
                ans=(ans+cnt1[u]*cnt2[v])%mod;
            if(dis1[u]+dis2[u]==dis1[t])
                ans=(ans+cnt1[v]*cnt2[u])%mod;
        }
    }
    cout<<ans%mod<<'\n';
    return;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}