inque表示是否在队列中。

path每个点统计最短路的条数。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,t,y;
int Last[2000005],Next[2000005],End[1000005],Len[2000005],dis[1000005],path[1000005];
bool inque[1000005];
queue<int> que;
void spfa(int x){
	for(int i = 1; i <= n; i++){
		dis[i] = 99999999;
		inque[i] = 0;
		path[i] = 0;
	}
	path[x] = 1;
	que.push(x);
	inque[x] = 1;
	dis[x] = 0;
	while(!que.empty()){
		int tp = que.front();
		que.pop();
		inque[tp] = 0;
		t = Last[tp];
		while(t != 0){
			y = End[t];
			if(dis[x] + Len[t] == dis[y]){
				path[y] += path[x];
				path[y] %= 100003;
			}else{
				if(dis[x] + Len[t] < dis[y]){
					dis[y] = dis[x]+Len[t];
					path[y] = path[x];
					path[y] %= 100003;
					if(!inque[y]){
						inque[y] = 1;
						que.push(y);
					}
				}
			}
			t = Next[t];
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	//memset(Len,0x3f,sizeof(Len));
	int a,b;
	for(int i = 1; i <= m; i++){
		scanf("%d%d",&a,&b);
		End[i] = b;
		Len[i] = 1;
		Next[i] = Last[a];
		Last[a] = i;
	}
	spfa(1);
	for(int i = 1; i <= n; i++){
		printf("%d\n",path[i]);
	}
	return 0;
}

请大佬查错