题目链接

最短路——最短路计数（spfa）

题目描述

给出一个 N 个顶点 M 条边的无向无权图，顶点编号为 1-N。问从顶点 1 开始，到其他每个点的最短路有几条。

输入格式

第一行包含 2 个正整数 N,M，为图的顶点数与边数。

接下来 M 行，每行 2 个正整数 x,y，表示有一条顶点 x 连向顶点 y 的边，请注意可能有自环与重边。

输出格式

共 N 行，每行一个非负整数，第 i 行输出从顶点 1 到顶点 i 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 ans mod 100003后的结果即可。如果无法到达顶点 i 则输出 0。

输入输出样例

输入

5 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5

输出

1 1 1 2 4

#include<bits/stdc++.h> using namespace std; const int mod=1e5+3; const int maxn=2000005; const int inf=0x3f3f3f3f; int n,m,x,y,ans; vector<int> f[maxn]; int dis[maxn],vis[maxn],cnt[maxn]; void spfa(int k) { queue<int> q; q.push(k); dis[k]=0; cnt[k]=1; vis[k]=1; while(!q.empty()){ int p=q.front(); q.pop(); vis[p]=0; for(int i=0;i<f[p].size();i++){ int t=f[p][i]; if(dis[t]>dis[p]+1){ dis[t]=dis[p]+1; cnt[t]=cnt[p]; if(!vis[t]){ vis[t]=1; q.push(t); } } else if(dis[t]==dis[p]+1){ cnt[t]=(cnt[t]+cnt[p])%mod; } } } } int main() { cin>>n>>m; for(int i=0;i<m;i++){ cin>>x>>y; f[x].push_back(y); f[y].push_back(x); } memset(dis,inf,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); spfa(1); for(int i=1;i<=n;i++){ cout<<cnt[i]<<endl; } return 0; }