AcWing传送门
洛谷传送门
题目大意
\(\qquad\)给一个无向图，边权都是\(1\)，求出以\(1\)为源点，到各个点(\(1\sim n\))的最短路数量
解题思路
\(\qquad\)边权都是\(1\)的图中最短路，我们选择用\(BFS\)解决这个问题
\(\qquad\)对于每个点\(j\)，我们进行以下讨论：（假设这个\(j\)在这轮\(BFS\)中由\(i\)点转移而来)
\(\qquad\)\(1.\)当\(dist_{\ j} < dist_{\ i} + 1\)的时候，由于队列的性质，\(点1\)到\(点j\)的若干条最短路中\(\color{Red}{\huge 必定没有i}\)，所以我们可以直接忽视这种情况
\(\qquad\)\(2.\)当\(dist_{\ j} \ge dist_{\ i} + 1\)的时候，我们继续分成两类
\(\qquad \qquad \color{#0000ff}{\large a.}\ \ \ \large dist_{\ j} = dist_{\ i} + 1\)
\(\qquad\)\(\qquad\)在这种情况下，代表着\(i\)可以是\(1\sim j\)的最短路中的一个点，但是还有其它点，这里根据 加法原理 就可以得出我们\(cnt_{\ j}\)应该加上\(cnt_{\ i}\)（因为从\(1\sim i\)的任意一条最短路，再加上\(i\sim j\)这条边，都属于\(1\sim j\)的最短路）。
\(\qquad \qquad \color{#0000ff}{\large b.}\ \ \ \large dist_{\ j} = dist_{\ i} + 1\)
\(\qquad\)\(\qquad\)在这种情况下，代表\(i\)是目前第一个可以更新\(j\)的点，所以\(j\)是第一次被更新，需要入队，其它的操作和分类\(\color{#0000ff}{\large a}\)都是一样的
代码
#include #include #include using namespace std;const int N = 1e5 + 10, M = N << 2, mod = 1e5 + 3;int dist[N], n, m, cnt[N];int h[N], e[M], ne[M], idx;void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}void bfs() { memset(dist, 0x3f, sizeof dist); queue q; dist[1] = 0, cnt[1] = 1, q.push(1); while (q.size()) { auto t = q.front(); q.pop(); for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + 1) { dist[j] = dist[t] + 1; cnt[j] = cnt[t]; q.push(j); } else if (dist[j] == dist[t] + 1) cnt[j] = (cnt[j] + cnt[t]) % mod; } }}int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ) { int u, v; scanf("%d%d", &u, &v); add(u, v), add(v, u); } bfs(); for (int i = 1; i <= n; i ++ ) printf("%d\n", cnt[i]); return 0;}