「一本通 3.2 练习 3」最短路计数

形式化题目

给定无向无权图 $G = (V, E)$ ， $V = \{1, 2, \dots, N\}$ ， $|E| = M$ ，允许重边（两条端点和方向都相同的边视为两条不同的边）。

对每个顶点 $i$ ，令 $\mathrm{dist}_i$ 为 1 到 $i$ 的最少边数，求有多少条长度为 $\mathrm{dist}_i$ 的路径，答案对 $100003$ 取模；若 $i$ 不可达则记 $0$ 。

下图是题面样例图（顶点 $1 \sim 5$ ，边 $1\text{-}2,\ 1\text{-}3,\ 2\text{-}3,\ 2\text{-}4,\ 3\text{-}4,\ 4\text{-}5 \times 2$ ），其中 $4 \to 5$ 之间的两条重边画成并列的两条：

graph LR
  n1((1)) --- n2((2))
  n1 --- n3((3))
  n2 --- n3
  n2 --- n4((4))
  n3 --- n4
  n4 -->|a| n5((5))
  n4 -->|b| n5

注意 $(2,3)$ 是同层横边： $\mathrm{dist}_2 = \mathrm{dist}_3 = 1$ ，它不会构成任何最短路的一部分；而 $4 \to 5$ 的重边会让到 5 的答案正好翻倍。

正解

思路

朴素做法是"先求距离、再枚举路径"：对每个点搜出所有 1 到它的路径，挑最短的计数。在分层图上用 DFS 枚举路径，路径条数本身就是答案，可以指数级增长，必然超时。瓶颈不在于"求距离"（BFS 已经是最优），而在于把路径计数当成了枚举路径：同一个前驱 $j$ 与到 $j$ 的所有最短路被重复走了很多遍。

注意到最短路有可加结构：一条以 $(j, i)$ 结尾的 1 到 $i$ 最短路，去掉最后这条边后，剩下的是 1 到 $j$ 的最短路，且 $\mathrm{dist}_j + 1 = \mathrm{dist}_i$ 。于是设 $cnt_i$ 为到 $i$ 的最短路条数，得到递推

cnt_1 = 1, \qquad cnt_i = \sum_{\substack{(j,i) \in E \\ \mathrm{dist}_j + 1 = \mathrm{dist}_i}} cnt_j

这是一条只依赖上一层的加法递推。而无权图的 BFS 按 $\mathrm{dist}$ 非降序访问顶点，出队顺序天然就是转移所需的拓扑序，所以求距离和递推计数可以合并成一次 BFS，不必显式建出最短路 DAG、也不必额外排序。

关键在于出队 $u$ 时它自己的 $cnt_u$ 是否已经收齐： $cnt_u$ 只被 $\mathrm{dist}_u - 1$ 层的点贡献，而第 $\mathrm{dist}_u - 1$ 层的点全部先于第 $\mathrm{dist}_u$ 层的 $u$ 出队，所以 $u$ 出队时 $cnt_u$ 一定完整，可以安全地传给下一层。

以样例为例，BFS 逐层推进的演算如下（ $\mathrm{dist}$ 即队列的层号）：

出队 $u$	$\mathrm{dist}_u$ / $cnt_u$	检查的邻居 $v$	命中分支	更新后 $cnt$
1	0 / 1	2	未访问	$cnt_2 = 1$
1	0 / 1	3	未访问	$cnt_3 = 1$
2	1 / 1	1	更浅，忽略	不变
2	1 / 1	4	未访问	$cnt_4 = 1$
2	1 / 1	3	$\mathrm{dist}_3 = 1 = \mathrm{dist}_2$ ，同层，忽略	不变
3	1 / 1	1	更浅，忽略	不变
3	1 / 1	4	已访问且 $\mathrm{dist}_4 = 1 + 1$ ，累加	$cnt_4 = 1 + 1 = 2$
3	1 / 1	2	同层（ $\mathrm{dist}_2 = 1$ ），忽略	不变
4	2 / 2	2	更浅，忽略	不变
4	2 / 2	3	更浅，忽略	不变
4	2 / 2	5	未访问（重边第一条）	$cnt_5 = 2$
4	2 / 2	5	已访问且 $\mathrm{dist}_5 = 2 + 1$ ，累加（重边第二条）	$cnt_5 = 2 + 2 = 4$
5	3 / 4	4	更浅，忽略（两条重边各一次）	不变

表格说明：每行是一次「出队 $u$ 后检查邻居 $v$ 」的完整记录，dist_u / cnt_u 是出队时 $u$ 的值。按 BFS 顺序把这张表读下来，可以看到 $u$ 出队时它的 $cnt_u$ 从未再被改动过——这正是「上一层点先出队」带来的不变式。可以看到 $cnt_4$ 由两个同层前驱 $2, 3$ 叠加得到， $cnt_5$ 则因为 $4$ 出队时遍历到两条重边而被累加两次，正好解释了样例输出的 1 1 1 2 4。

实现上有两条分支，都写在遍历 adj[u] 的内层循环里：

dist[v] < 0（尚未访问）：说明 $v$ 的最短距离刚被确定为 $\mathrm{dist}_u + 1$ ，此刻把 $cnt_v \leftarrow cnt_u$ 作为初值，并把 $v$ 入队。这里用 -1 兼任"未访问"标记，比额外开 visited 数组省一次空间和一次判断（顶点 1 的 $\mathrm{dist} = 0$ ，不会与 -1 混淆）。
dist[v] == dist[u] + 1（已访问且正好在下一层）： $(u,v)$ 是递推求和里的一项，执行 $cnt_v \mathrel{+}= cnt_u$ 。

其余情形都不满足 $dist$ 关系，不参与最短路的构成，直接忽略： $v$ 更浅（ $dist_v < dist_u$ ）或与 $u$ 同层（ $dist_v = dist_u$ ）都会被排除，在表格中一律记为 忽略。在无权 BFS 中不会出现 $dist_v > dist_u + 1$ ，因为 $v$ 至多比 $u$ 晚一层被发现。累加时立刻对 $100003$ 取模，避免答案位数膨胀。由于每条无向边在两个邻接表里各存一次，重边会导致 $u$ 出队时对同一个 $v$ 执行分支两次，第二次恰好走"已访问 + 下一层"分支完成翻倍，这也是样例中 $4 \to 5$ 两条重边被正确计成两条路径的原因。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 14:52
# update_at: 2026-09-30 14:52

import sys
from collections import deque

MOD = 100003  # 题面要求的取模值


def bfs_count(adj: list[list[int]], n: int) -> list[int]:
    """从顶点 1 出发 BFS，返回每个顶点被多少条最短路走到（对 MOD 取模）。"""
    dist = [-1] * (n + 1)  # -1 表示尚未访问，同时充当"层号"
    cnt = [0] * (n + 1)
    dist[1], cnt[1] = 0, 1

    queue = deque([1])
    while queue:
        u = queue.popleft()
        du, cu = dist[u], cnt[u]  # 出队时 cnt[u] 已收齐同一层全部前驱的贡献
        for v in adj[u]:
            if dist[v] < 0:  # 第一次到达 v：这正是最短路，层号由 u 决定
                dist[v] = du + 1
                cnt[v] = cu
                queue.append(v)
            elif dist[v] == du + 1:  # v 与 u 同属"u 的下一层"，再多一条最短路
                cnt[v] = (cnt[v] + cu) % MOD

    return cnt[1:]


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    n, m = int(next(it)), int(next(it))

    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = int(next(it)), int(next(it))
        adj[u].append(v)
        adj[v].append(u)  # 无向图，两个方向都要存

    sys.stdout.write('\n'.join(map(str, bfs_count(adj, n))) + '\n')


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 04:41
 * update_at: 2026-10-05 04:41
 */
// main.cpp：「一本通 3.2 练习 3」最短路计数
// 无向无权图（允许重边）：BFS 按层推进求最短距离，同时递推统计到每个点的最短路条数。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXN = 100005; // 顶点数上限 N <= 100000
const int MOD = 100003;  // 题面要求的取模值

// adj[u]：与顶点 u 相邻的所有顶点（一条无向边在两个邻接表里各存一次，重边原样保留）
vector<int> adj[MAXN];

// dist[u]：从顶点 1 到 u 的最短边数，-1 表示尚未访问（同时充当"层号"）
int dist[MAXN];

// cnt[u]：从顶点 1 到 u 的最短路条数，边算边对 MOD 取模
ll cnt[MAXN];

// 从顶点 1 出发做 BFS，并同步递推最短路条数。
// 关键不变式：dist 相同的点按 BFS 出队顺序处理，第 dist[u]-1 层的点全部先于 u 出队，
// 所以出队 u 时 cnt[u] 已经收齐全部前驱的贡献，可以安全地传给下一层。
void bfs_count(ll n) {
    for (ll i = 1; i <= n; i++) {
        dist[i] = -1;
        cnt[i] = 0;
    }

    dist[1] = 0;
    cnt[1] = 1; // 顶点 1 到自己算 1 条最短路，输出第 1 行为 1

    queue<ll> q; // BFS 队列，出队顺序按 dist 非降
    q.push(1);

    while (!q.empty()) {
        ll u = q.front();
        q.pop();

        ll du = dist[u];
        ll cu = cnt[u];
        ll deg = adj[u].size();

        for (ll i = 0; i < deg; i++) {
            ll v = adj[u][i];

            if (dist[v] == -1) {
                // 第一次到达 v：最短路长度由 u 确定为 du + 1，先把 cnt[u] 作为初值
                dist[v] = du + 1;
                cnt[v] = cu;
                q.push(v);
            } else if (dist[v] == du + 1) {
                // v 正好是 u 的下一层：多出一条经过 (u, v) 的最短路
                // 重边会让同一对 (u, v) 再次落到这里，语义正是两条不同的路径
                cnt[v] = (cnt[v] + cu) % MOD;
            }
            // 其余情形（v 更浅或与 u 同层）都不构成最短路，直接忽略
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m;
    cin >> n >> m;

    for (ll i = 0; i < m; i++) {
        ll u, v;
        cin >> u >> v;
        adj[u].push_back(v); // 无向图，两个方向都要存
        adj[v].push_back(u);
    }

    bfs_count(n);

    for (ll i = 1; i <= n; i++) {
        cout << cnt[i] << '\n'; // 不可达点的 cnt 保持 0，输出自然为 0
    }

    return 0;
}

复杂度

时间复杂度： $O(N + M)$ 。每个顶点入队、出队各一次，每个邻接表项被检查一次，检查是 $O(1)$ 。
空间复杂度： $O(N + M)$ 。邻接表存 $2M$ 个整数，dist、cnt 各 $O(N)$ 。

总结

带权最短路的计数要靠 Dijkstra/DAG 上的拓扑 DP；本题权值全为 1，BFS 的层序就是拓扑序，于是"求距离"和"计数递推"能合并进同一次 BFS。
递推式 $cnt_i = \sum_{\mathrm{dist}_j + 1 = \mathrm{dist}_i} cnt_j$ 的两个分支在代码中分别是 “首次到达时赋值"和"同层前驱累加”，用 dist[v] < 0 与 dist[v] == dist[u] + 1 区分；同层横边（如样例的 $(2,3)$ ）和自环都会被这两条判断自动排除。
重边是这题的隐藏坑：按邻接表原样存两条边，第二次遍历会落到累加分支上，语义与"两条不同路径"一致。
计数必须边加边取模；不可达点 cnt 保持 0，输出自然为 0。

「一本通 3.2 练习 3」最短路计数

目录

形式化题目

正解

思路

代码

复杂度

总结