看题解用了spfa做 其他都过了 剩下#6 求大佬指点一下 谢谢

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N = 1e6+10,M = 4e6+10,mod = 100003;
int n, m;
int e[M],w[N],h[N], ne[M], idx;
int dist[N],ans[N];
bool st[N];

void add(int a,int b) {
	
	e[idx] = b;
	w[idx] = 1;
	ne[idx] = h[a]; 
	h[a] = idx++;
}

void spfa() {
	memset(dist, 0x7f, sizeof dist);
	queue<int> q;
	q.push(1);
	dist[1] = 0;
	st[1] = true;
	ans[1] = 1;

	while (q.size()) {
		int t = q.front();
		q.pop();
		st[t] = false;

		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			
			if(dist[j] > dist[t] + w[i]) {
				dist[j] = dist[t] + w[i];
				ans[j] = ans[t];//更新最短路数量
				if (!st[j]) {
					q.push(j);
					st[j] = true;
				}
			}
			else if (dist[j] == dist[t] + w[i]) {
				ans[j] = (ans[j] + ans[t]%mod) % mod;//累加最短路径数量
			}
			
			
		}
	}
	for (int i = 1; i <= n; i++) {
		printf("%d\n", ans[i]);
	}

}

int main() {
	memset(h, -1, sizeof h);
	cin >> n >> m;
	while (m--) {
		int a, b; 
		scanf("%d%d", &a, &b);
		add(a, b);
		add(b, a);
	}
	spfa();
	return 0;
}