题目P1144.

#include <bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f,mod=100003,N=2e6+5;

int n,m,s,head[N],dis[N],cnt,ans[N];
bool inf[N];
struct l{
	int next;
	int to;
	int w;
}e[N];

void adde(int u,int a)
{
	e[++cnt].to=a;
	e[cnt].next=head[u];
	head[u]=cnt;
}

void SPFA()
{
	queue<int> q;
	dis[1]=0;
	q.push(1);
	inf[1]=1;
	ans[1]=1;
	while (!q.empty())
	{
		int u=q.front();
		q.pop();
		inf[u]=0;
		for (int i=head[u];i!=-1;i=e[i].next)
		{
			if (dis[u]+1<dis[e[i].to])
			{
				ans[e[i].to]=ans[u];
				dis[e[i].to]=dis[u]+1;
				if (inf[e[i].to]!=1)
				{
					q.push(e[i].to);
					inf[e[i].to]=1;
				}
			}
			else if (dis[u]+1==dis[e[i].to])
			{
				ans[e[i].to]+=ans[u];
				ans[e[i].to]%=mod;
			}
		}
	}
}

int main()
{
	cin >>n>>m;
	memset(head,-1,sizeof(head));
	memset(dis,INF,sizeof(dis));
	for (int i=1;i<=m;i++)
	{
		int u,a;
		cin >>u>>a;
		adde(u,a);
		adde(a,u);
	}
	SPFA();
	for (int i=1;i<=n;i++)
	{
		cout <<ans[i]<<endl;
	}
	return 0;
}

新加的测试点TLE。