代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005,M = 4000005,INF = 0x3fffffff,mod = 100003;

// 链式前向星
struct edge{
	int v,prev;
}edges[M];
int tail[N],tot;
void add_edge(int u,int v){
	edges[++tot] = {v,tail[u]};
	tail[u] = tot;
}

int dis[N];
int cnt[N];
bool f[N];
void bf(){
	queue<int> q;
	q.push(1);
	f[1] = 1;
	while (!q.empty()){
		int u = q.front();
		q.pop();
		f[u] = 0;
		for (int i = tail[u];i;i = edges[i].prev){
			int v = edges[i].v;
			if (dis[u] + 1 == dis[v])	cnt[v] += cnt[u],cnt[v] %= mod;	// 前面能走多少次，我就能走多少次
			else if (dis[u] + 1 < dis[v]){
				cnt[v] = cnt[u];	// 有更短的路径，继承爸爸的路径数
				dis[v] = dis[u] + 1;
				if (!f[v])	q.push(v),f[v] = 1;
			}
//			printf("u: %d v: %d cnt: %d dis: %d\n",u,v,cnt[v],dis[v]);
		}
	}
}
int main(int argc, char **argv){
	fill(dis,dis + N,INF);
	cnt[1] = 1;

	int n,m;
	cin >> n >> m;
	dis[1] = 0;
	for (int i = 0;i < m;i++){
		int x,y;
		cin >> x >> y;
		// 无向图
		add_edge(x,y);
		add_edge(y,x);
	}
	bf();
	for (int i = 1;i <= n;i++){
		printf("%d\n",cnt[i]);
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;
//Dijkstra优化算法+邻接表存储 
vector<int> g[2000010];
const int mod=100003;
int dist[2000010],vis[2000010],cnt[20000010];
//dist[]表示最短路长度，vis[]表示是否遍历过，cnt[]表示最短路数量 
int n,m;
void bfs(int s){
	queue<int> q;
	q.push(s);
	dist[s]=0;//自己到自己的最短路长度为0 
	cnt[1]=1;//自己到自己有一条路径 
	while(!q.empty()){
		int u=q.front();
		q.pop();
		//cout<<u<<'\n';
		//vis[u]=0;
		int sizes=g[u].size();
		for(int k=0;k<sizes;k++){//遍历可以到达的节点 
			int v=g[u][k];
			//cout<<v<<'\n';
            if(dist[u]+1==dist[v]){//当最短路长度相等时 
                cnt[v]+=cnt[u];//最短路数量++ 
                cnt[v]%=mod;//%mod 
            }
			if(dist[u]+1<dist[v]){//当发现更短路径时 
                cnt[v]=cnt[u];//替换当前最短路长度的数量 
				dist[v]=dist[u]+1;//更新最短路长度 
				if(vis[v]!=1){
					q.push(v);//未被遍历过时加入 
					vis[v]=1;
				}
			}
		}	
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		//无向图连接(双向) 
		g[u].push_back(v);
		g[v].push_back(u);
	}
	memset(dist,1e9+7,sizeof(dist));//初始化极大值(INF,1e9+7,1e18...等) 
    bfs(1);
	for(int i=1;i<=n;i++){
		cout<<cnt[i]<<'\n';
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
vector<int>ppp[2000010];
int pmin[2000010],vis[2000010],ans[20000010],n,m,x,y;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		ppp[x].push_back(y);
		ppp[y].push_back(x);
	}
	for(int i=0;i<2000010;i++)pmin[i]=1000000001;
	queue<int>q;
	q.push(1),pmin[1]=0,ans[1]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int p=0;p<ppp[x].size();p++){
			if(pmin[x]+1==pmin[ppp[x][p]]){
				ans[ppp[x][p]]+=ans[x];
				ans[ppp[x][p]]%=100003;
			}
			if(pmin[x]+1<pmin[ppp[x][p]]){
				ans[ppp[x][p]]=ans[x],pmin[ppp[x][p]]=pmin[x]+1;
				if(vis[ppp[x][p]]!=1){
					q.push(ppp[x][p]);
					vis[ppp[x][p]]=1;
				}
			}	
		}
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
	return 0;
}