水题链接：https://www.luogu.org/problemnew/show/P1144
这道题就是很水啊，水到我居然不用最短路算法就做了出来。因为每条边的权值都为1，最短路计数，无异于遍历整张图，记录有多少个结点可以到达这个点，且路径长度为最小的那个。用BFS，保证第一次访问到结点时的路径长度就是到起点的最短路，后面只需要加个条件判断就行。其实SPFA、Dijkstra堆优化也可以，就是懒得去写，他只需要求最短路并且统计最短路到每个结点的次数就可以了（当然因为本题的边权都为1）。另外他说有重边，这个没关系，还说有自环，就吓到我了（怎么可能），所以加上一个当前弧优化QwQ。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 5 using namespace std; 6 7 inline int get_num() { 8 int num = 0; 9 char c = getchar(); 10 while (c < '0' || c > '9') c = getchar(); 11 while (c >= '0' && c <= '9') 12 num = num * 10 + c - '0', c = getchar(); 13 return num; 14 } 15 16 const int maxn = 1e6 + 5, maxm = 2e6 + 5, inf = 0x3f3f3f3f, mod = 1e5 + 3; 17 18 int head[maxn], eid; 19 20 struct Edge { 21 int v, next; 22 } edge[2 * maxm]; 23 24 inline void insert(int u, int v) { 25 edge[++eid].v = v; 26 edge[eid].next = head[u]; 27 head[u] = eid; 28 } 29 30 int dist[maxn], cnt[maxn], vis[maxn]; 31 32 queue<int> q; 33 34 inline void bfs() { 35 memset(dist, inf, sizeof(dist)); 36 dist[1] = 0, cnt[1] = 1; 37 q.push(1); 38 vis[1] = 1; 39 while (!q.empty()) { 40 int u = q.front(); 41 q.pop(); 42 for (int& p = head[u]; p; p = edge[p].next) { 43 int v = edge[p].v; 44 if (dist[v] == dist[u] + 1) cnt[v] += cnt[u]; 45 if (dist[v] == inf) dist[v] = dist[u] + 1, cnt[v] = cnt[u]; 46 if (cnt[v] > mod) cnt[v] -= mod; 47 if (!vis[v]) { 48 q.push(v); 49 vis[v] = 1; 50 } 51 } 52 } 53 } 54 55 int main() { 56 int n = get_num(), m = get_num(); 57 for (int i = 1; i <= m; ++i) { 58 int x = get_num(), y = get_num(); 59 insert(x, y); 60 insert(y, x); 61 } 62 bfs(); 63 for (int i = 1; i <= n; ++i) 64 printf("%d ", cnt[i]); 65 return 0; 66 }