其实这道题目的正解应该是spfa里面加一些处理，，然而，，然而，，既然它是无权图，，那么就直接bfs了，用一个cnt记录一下每一个点的方案数，分几种情况讨论一下转移，最后输出cnt即为结果。。
题目中所说的重边和自环啥的没看出来有啥影响。。
1 #include2 #include 3 #include 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\n", cnt[i]);57 }58 59 return 0;60 }