This is a 平平无奇 的 c++迪杰斯特拉+堆优化

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
int h[1000006],nxt[2000006],to[1000006],
dis[1000006],b[1000006],num[1000006],cnt;
inline int read(){
	char ch=getchar(); 
	int x=0,f=1;
	while((ch>'9'||ch<'0')&&ch!='-')
		ch=getchar();
	if(ch=='-')
	{
		f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9')
	{
    	x=x*10+ch-'0';
    	ch=getchar();
	}
	return x*f;
}
void add(int u,int v){
	cnt++;
	nxt[cnt]=h[u];
	h[u]=cnt;
	to[cnt]=v;
}
int main(){
	int n,m,u,v;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		dis[i]=0x3fffffff;
	}
	for(int i=1;i<=m;i++){
		u=read(),v=read();
		add(u,v);
		add(v,u);
	}
	dis[1]=0;
	num[1]=1;
	
	priority_queue<PII> q;
	q.push({0,1});
	while(!q.empty()){
		u=q.top().second;
		q.pop();
		for(int j=h[u];j;j=nxt[j]){
			if(dis[u]+1<dis[to[j]]){
				dis[to[j]]=dis[u]+1;
				num[to[j]]=1;
				q.push({-dis[to[j]],to[j]});
			}else if(dis[u]+1==dis[to[j]]){
				num[to[j]]++;
				num[to[j]]%=100003;
				q.push({-dis[to[j]],to[j]});
			}
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d\n",num[i]%100003);
	}
	return 0;
}