6538 #include"stdafx.h" #include <iostream> #include <vector> #include <queue> using namespace std; const int maxn = 0x7fffffff; // 0x3f不够。。。 int n, m, x, y; int vis[1000010],dis[1000010], ans[1000010]; //ans存最短路个数 vector<int> g[1000010]; queue<int> q; inline void spfa(int x) { for(int i=1; i<=n; i++)dis[i] = maxn; q.push(x); vis[x] = 1; ans[x] = 1; // 本身为1个最短路 dis[x] = 0; while (!q.empty()) { u = q.front(); q.pop(); for (int i = 0; i < g[u].size(); i++) { v = g[u][i]; if (dis[v] > dis[u] + 1) //如果满足u到v的距离比原本到v的距离小,则更新 { dis[v] = dis[u] + 1; ans[v] = ans[u]; // v点和u点在一条路上,所以v的最短路个数等于u的最短路个数 if (!vis[v]) vis[v] = 1, q.push(v); } else if (dis[v] == dis[u] + 1) ans[v] = (ans[v] + ans[u]) % 100003; // 该点最短路个数为u最短路个数+v最短路个数 } vis[u] = 0; } } int main() { cin >> n >> m; while (m--) { cin >> x >> y; g[x].push_back(y),g[y].push_back(x); } spfa(1); for (int i = 1; i <= n; i++) cout << ans[i] << endl; return 0; }