最短路计数--应用spfa算法

给出一个 N 个顶点 M 条边的无向无权图，顶点编号为 1 到 N。

问从顶点 1 开始，到其他每个点的最短路有几条。

输入格式

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

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

输出格式

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

如果无法到达顶点 i 则输出 0。

数据范围

1≤N≤105,

1≤M≤2×105

输入样例：

5 7

1 2

1 3

2 4

3 4

2 3

4 5

4 5

输出样例：

1

1

1

2

4

思路

cnt数组记录到每个点的最短路条数总和。

spfa中每一次更新距离时可判断

如果 dist[j]=dist[t]+1 说明此时 从1到j的最短路一定被其他点更新过了而不是t，cnt[j]=cnt[j]+cnt[t];

else dist[j[>dist[t]+1 说明此时 从1到j的最短路未被更新，就可以用t点更新 cnt[j]=cnt[t]

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=5e5+10,eps=1e5+3;
int h[N],ne[N],e[N],idx;
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dist[N],st[N],cnt[N];
void bfs(){
	memset(dist,0x3f,sizeof dist);
	queue<int> q;q.push(1);st[1]=1;cnt[1]=1,dist[1]=0;
	while(q.size()){
		int t=q.front();q.pop();st[t]=0;
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];
			if(dist[j]==dist[t]+1) cnt[j]=(cnt[j]+cnt[t])%eps;
			else if(dist[j]>dist[t]+1) {
				dist[j]=dist[t]+1;
				cnt[j]=cnt[t];
				if(st[j]!=1) q.push(j);
			} 
		} 
	}
}
int main(){
	cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m --){
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    bfs();
    for (int i = 1; i <= n; i ++) cout << cnt[i] << endl;
    return 0;
}