RT，代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
queue<int> q, step;
const int mod = 100003;
int n, m, u, v, ans[1000001], head[1000001], minn[1000001], cnt;
bool vis[1000001];
struct edge{
	int to;
	int next;
}e[2000001];
void add(int u, int v)
{
	e[++cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}
int main()
{
	ans[1] = 1;
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		cin >> u >> v;
		if(u != v)
		{
			add(u, v);
			add(v, u);
		}
	}
	vis[1] = 1;
	memset(minn, 9999, sizeof(minn));
	minn[1] = 0;
	q.push(1);
	step.push(1);
	while(!q.empty())
	{
		int st = step.front(), now = q.front();
		step.pop();
		q.pop();
		for(int i = head[now]; i; i = e[i].next)
		{
			if(minn[now] + 1 < minn[e[i].to])
			{
				minn[e[i].to] = minn[now] + 1;
				ans[e[i].to] = ans[now] % mod;
				if(!vis[e[i].to])
				{
					vis[e[i].to] = 1;
					q.push(e[i].to);
				}
			}
			else if(minn[now] + 1 == minn[e[i].to])
			{
				ans[e[i].to] += ans[now];
				ans[e[i].to] %= mod;
				if(!vis[e[i].to])
				{
					vis[e[i].to] = 1;
					q.push(e[i].to);
				}
			}
		}
	}
	for(int i = 1; i <= n; i++)
		cout << ans[i] << endl;
	return 0;
}

评测记录