其实这道题目的正解应该是spfa里面加一些处理，，然而，，然而，，既然它是无权图，，那么就直接bfs了，用一个cnt记录一下每一个点的方案数，分几种情况讨论一下转移，最后输出cnt即为结果。。
题目中所说的重边和自环啥的没看出来有啥影响。。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 const int maxn = 100000 + 500; 6 const int mod = 100003; 7 int que[maxn]; 8 bool vis[maxn]; 9 int last[maxn], pre[5 * maxn], other[5 * maxn]; 10 int dis[maxn], cnt[maxn]; 11 int n, m; 12 int x, y; 13 int tot = 0; 14 void bfs(int s) { 15 memset(dis, 127, sizeof(dis)); 16 dis[s] = 1; 17 cnt[s] = 1; 18 int h = 0, t = 1; 19 que[1] = s; 20 while (h < t) { 21 h = (h + 1) % maxn; 22 int cur = que[h]; 23 for (int p = last[cur]; p; p = pre[p]) { 24 int q = other[p]; 25 if (dis[q] == 0) { 26 dis[q] = dis[cur] + 1; 27 cnt[q] = cnt[cur]; 28 t = (t + 1) % maxn; 29 que[t] = q; 30 } else if (dis[q] > dis[cur] + 1) { 31 dis[q] = dis[cur] + 1; 32 cnt[q] = cnt[cur]; 33 t = (t + 1) % maxn; 34 que[t] = q; 35 } else if (dis[q] == dis[cur] + 1) { 36 cnt[q] = (cnt[q] + cnt[cur]) % mod; 37 } 38 } 39 } 40 } 41 void add(int x, int y) { 42 tot++; 43 pre[tot] = last[x]; 44 last[x] = tot; 45 other[tot] = y; 46 } 47 int main () { 48 scanf("%d %d", &n, &m); 49 for (int i = 1; i <= m; i++) { 50 scanf("%d %d", &x, &y); 51 add(x, y); 52 add(y, x); 53 } 54 bfs(1); 55 for (int i = 1; i <= n; i++) { 56 printf("%d ", cnt[i]); 57 } 58 59 return 0; 60 }