洛谷P1144标准的题目名叫“最短路计数”是我刷图论入门题单时绕不开的一道题。题目本身不复杂给你一张可能有重边和自环的无向无权图从点1出发问到达每个点的最短路径一共有多少条结果对100003取模。但这道题在洛谷的讨论区里常年热度不减评论区总能见到“为什么BFS就能计数”“重边要不要特判”这类问题甚至我自己第一次写就漏掉了等距更新的情况。这篇不是把官方题解复述一遍而是想把我从抄代码到真正想明白的全过程拆开为什么最短路计数本质是个动态规划BFS为什么恰好能给出合法转移顺序链式前向星和Java怎么写才不爆内存以及那些提交了五六次才发现的小坑。适合刚学完BFS和基础图论、准备刷洛谷题单或校赛的读者。1. 题目到底在问什么先看清这题长什么样1.1 输入、输出与真正的数据规模输入格式非常常规第一行两个正整数 n、m表示点数和边数接下来 m 行每行两个正整数 u、v表示一条无向边。输出要求从 1 号点出发第 i 行输出到 i 号点的最短路条数对 100003 取模后的值。如果从 1 号点无法到达 i那么输出 0。有个新手经常会问的问题正好可以在这里说清楚在洛谷提交代码时数据是评测系统通过标准输入喂给程序的你不需要自己去读本地文件更不需要关心“数据放在哪个文件夹”。你只要用标准输入把数据读完用标准输出把答案打印出来剩下的全部交给评测机。所以别在这个问题上浪费哪怕一分钟。再说数据范围。我印象中洛谷这道题的数据范围很“大胃王”N 和 M 可以到百万量级至少不是那种让你随随便便开邻接矩阵的小图。这意味着两件事第一邻接矩阵想都不用想O(n²) 内存直接爆炸第二输入输出量非常大如果你用不关同步的 cin 加上 endl大概率会收获一个 TLE。后文我会专门说怎么在这一步上省时间。1.2 这题难在哪不是求最短而是数最短如果只求最短长度那就是最基础的 BFS维护一个 dist 数组第一次访问到某个点时就赋值最后输出 dist[i] 即可。但这道题多了一个字“条数”。这样就要求我们不能只记“最短有多短”还得记“最短的来路有几条”。举个例子点 1 到点 3 的最短距离是 2但是走法可能有两种1→2→3 和 1→4→3。只要这两条路的长度都是 2那么在答案里cnt[3] 就应该是 2。如果两条路里有公共前缀比如 1→2 有两种走法之后 2→3 只有一条那么 cnt[3] 应该是 2 而不是 1因为两条完整路径仍然是不同的路径。这个“计数”的要求是整道题的核心门槛。很多人第一反应是我 BFS 跑一遍把所有最短路径都枚举出来不就行了对于小图可以但百万级别的图里路径数量是指数级增长的你根本枚举不完。所以必须用动态规划式的累加来统计而不是真的去把路径一条一条列出来。1.3 题目在算法题单里的位置如果你看过洛谷的动态规划题单会发现偶尔有人把 P1144 也放进去讨论。它明明是一道图论题为什么能跟 DP 扯上关系因为最短路计数本身就是“在有向无环图上的路径计数”只是这个 DAG 不是题目直接给你的而是由“距离源点更近”这个关系隐式定义的。换句话说你可以把每个点理解成一层一层推进的状态从点 1 开始距离为 1 的点由距离为 0 的点转移过来距离为 2 的点由距离为 1 的点转移过来。这个过程和图上的拓扑排序非常相似只不过拓扑序恰好由 BFS 的访问顺序代替了。所以它既出现在“图论最短路”题单里也经常被拿来当作“计数 DP”的入门例子。理解了这一点后面很多题你都会豁然开朗。2. 为什么最短路计数本质上是个DP2.1 先写出那个核心方程不管是 BFS 还是 Dijkstra最短路计数都逃不开下面这个转移逻辑对于一条从 u 出发到达 v 的边如果当前记录的最短距离满足 dist[v] dist[u] 1那么说明“从 1 到 u 的最短路再接上 u→v 这条边”就是一条从 1 到 v 的最短路。于是应该有cnt[v] cnt[u]如果 v 还没有被访问过也就是说 dist[v] 还是无穷大或者 -1那么第一个发现它的 u 会确定一个最短距离此时 cnt[v] cnt[u]。之后再遇到其他 u 满足 dist[v] dist[u] 1就让 cnt[v] 继续累加。这个方程看起来平平无奇但它就是整道题的灵魂。你需要先知道所有靠近源点的点的 cnt才能算出当前点的 cnt。这不就是典型的动态规划状态转移吗只是它的转移方向被“到源点的距离”严格排好了序不允许有环。2.2 为什么BFS天然满足转移顺序BFS 在无向无权图里是按“层”扩展的先把距离为 1 的所有点访问完再访问距离为 2 的所有点依次类推。这个特性保证了一个点第一次被访问到时它拿到的距离就是全局最短距离。因为在无权图中不可能存在一条路径比 BFS 先到达的层数还要短。有了这个保证之后计数就顺理成章了。当你在处理某一个点时所有可能向它提供最短路径的前驱点距离一定比它小 1而这些前驱点早就已经出队、早就已经把自己的 cnt 计算完了。于是当前点可以放心地累加所有前驱点的 cnt不会出现“某个前驱还没算好就急着给当前点加数”的情况。你可以把这个过程理解成发传单点 1 手上有 1 张传单它发给每个邻居每个邻居拿到传单后再按自己的传单张数复制给下一层。因为 BFS 保证传单永远是从近处往远处传递没人会在传单还没到齐的时候私自统计所以最后每个人手里的传单数量就是正确的方案数。2.3 为什么DFS直接做容易出错有些初学者会想BFS 能做DFS 是不是也能做我搜一遍图遇到满足 dist[v] dist[u] 1 就计数不就行了问题是 DFS 的访问顺序不是按距离递增的。举个例子DFS 可能先从一条长路径绕到 v此时给 v 赋了一个比较大的 dist之后再从一条更短路径绕回 v你确实可以更新 dist[v]但问题是之前已经基于那个错误的大 dist给 v 的后续节点传递过 cnt 了。虽然你可以强行回溯重新计算但在一个百万节点、可能存在环的图里这种反复更新的复杂度完全不可控而且极容易重复计数。所以最短路计数题基本不会用 DFS 硬搜而是用 BFS 或 Dijkstra 这一类“能保证按距离递增顺序处理节点”的算法。3. 完整实现从邻接表设计到能交的代码3.1 先解决存储为什么用链式前向星而不是vector嵌套看到 n 和 m 都是百万量级第一件事就是选存储结构。用邻接矩阵一个 n×n 的二维数组哪怕每个元素只占 1 字节1e6×1e6 那也是 1TB 量级想都别想。用 vectorvector 理论上可行但每个 vector 对象本身就有不小的内存开销。假设 n1e6光 100 万个 vector 对象就可能吃掉 24MB 左右再加上存储边关系的 int整体大约 40MB 起步虽然勉强能过但如果你对内存比较紧张或者遇到频繁 push_back 导致的动态扩容还是有点心疼。链式前向星是我在竞赛里更喜欢的方案。它本质上是静态链表head[u] 指向 u 的第一条边在 edge 数组里的下标edge 数组里的每个元素记录两个信息这条边通向哪个点 to以及同起点的下一条边叫什么 next。加边时用头插法新边永远插在 head[u] 的位置。整张图只需要两个数组内存非常紧凑。存储方式空间开销大致适用场景邻接矩阵O(n²)只有小图能用本题直接爆掉vectorvector 约40MB左右能过但容器开销和扩容有额外成本链式前向星head数组4MB edge数组约32MB本类大数据图的常用稳定方案3.2 C代码BFS计数模版下面这份是我实际提交时用的版本。数组大小按 N≤10^6、M≤2×10^6 来开如果你确认题目数据范围更小适当缩小也可以但开大了并不影响正确性只是多用一点内存。#include bits/stdc.h using namespace std; const int MAXN 1000005; const int MAXM 2000005; const int MOD 100003; struct Edge { int to, next; } edge[MAXM 1]; // 无向边要存两条方向所以开两倍 int head[MAXN], tot; int dist[MAXN], cnt[MAXN]; int q[MAXN], headq, tailq; // 直接用数组模拟队列比 std::queue 更省内存也更稳 inline void addEdge(int u, int v) { edge[tot] {v, head[u]}; head[u] tot; } // 快读输入量很大时getchar 手写解析比 scanf 还要快一截 inline int read() { int x 0; char c getchar(); while (c 0 || c 9) c getchar(); while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x; } int main() { int n read(), m read(); for (int i 0; i m; i) { int u read(), v read(); addEdge(u, v); addEdge(v, u); } memset(dist, -1, sizeof(dist)); dist[1] 0; cnt[1] 1; q[tailq] 1; while (headq tailq) { int u q[headq]; for (int i head[u]; i; i edge[i].next) { int v edge[i].to; if (dist[v] -1) { // 第一次到达直接继承当前点的方案数 dist[v] dist[u] 1; cnt[v] cnt[u]; q[tailq] v; } else if (dist[v] dist[u] 1) { // 距离相等说明发现新的最短路累加方案数 cnt[v] (cnt[v] cnt[u]) % MOD; } } } for (int i 1; i n; i) { printf(%d\n, cnt[i]); } return 0; }这里有个顺序问题我特别说一下判断dist[v] -1必须在前判断等距累加在后。原因是当 v 第一次被访问时它的 dist 会从 -1 变成某个具体值。如果你把等距判断写在前面第一次访问时 dist[v] 等于 -1而 -1 显然不等于 dist[u] 1程序就会跳过累加直接走到dist[v] -1分支里看起来好像没错。但如果有重边场景会变得非常微妙。总之这个 if 分支的顺序就是算法正确性的一部分不是随便写的。3.3 如果用Java写要注意什么Java 写这种大输入量的题最怕的就是 Scanner。StreamTokenizer 或者自定义快读是必需品。其次邻接表别用 ArrayListArrayList 嵌套内存开销大而且慢更推荐直接用三个一维数组模拟链式前向星。import java.io.*; import java.util.*; public class Main { static final int MOD 100003; static int[] head, to, nxt; static int tot; static void add(int u, int v) { to[tot] v; nxt[tot] head[u]; head[u] tot; } public static void main(String[] args) throws IOException { StreamTokenizer in new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n (int) in.nval; in.nextToken(); int m (int) in.nval; head new int[n 1]; to new int[2 * m 5]; nxt new int[2 * m 5]; for (int i 0; i m; i) { in.nextToken(); int u (int) in.nval; in.nextToken(); int v (int) in.nval; add(u, v); add(v, u); } int[] dist new int[n 1]; int[] cnt new int[n 1]; Arrays.fill(dist, -1); dist[1] 0; cnt[1] 1; QueueInteger q new ArrayDeque(); q.add(1); while (!q.isEmpty()) { int u q.poll(); for (int e head[u]; e ! 0; e nxt[e]) { int v to[e]; if (dist[v] -1) { dist[v] dist[u] 1; cnt[v] cnt[u]; q.add(v); } else if (dist[v] dist[u] 1) { cnt[v] (cnt[v] cnt[u]) % MOD; } } } StringBuilder sb new StringBuilder(); for (int i 1; i n; i) { sb.append(cnt[i]).append(\n); } System.out.print(sb); } }Java 版本里我保留了 ArrayDeque 而不是 LinkedList因为在大量出队入队的场景下 ArrayDeque 的常数更小。输出用 StringBuilder 一次性拼好也比逐行 System.out.println 快很多。4. 提交五次才过的坑自环、重边、取模与输入4.1 自环到底要不要特判自环就是 u 到 u 的一条边。很多人的第一反应是这会不会让 cnt[u] 自己加自己导致答案爆炸实际上不会。因为我们要判断的是dist[v] dist[u] 1而 v 和 u 是同一个点时dist[u] 不可能等于 dist[u] 1。所以自环在 BFS 计数里天然被忽略不需要额外特判。就算自环出现在起点 1 上dist[1] 是 0检查到自环时条件不成立cnt[1] 不会被改动。所以你在实现时完全不用管自环放心让 BFS 去遍历即可。4.2 重边带来的“看似重复”其实是正确行为重边的坑更隐蔽。假设 u 和 v 之间有两条平行边你在遍历 u 的邻接表时第一条边让 v 第一次入队dist[v] 被赋为 dist[u]1cnt[v] cnt[u]。紧接着第二条边又指向 v此时 dist[v] 已经是 dist[u]1于是进入等距分支cnt[v] 再次加了一次 cnt[u]。这不就重复计数了吗答案是没有。因为这两条边是两条不同的边从 u 到 v 的“走法”本来就因为边的不同而不同。比如 u 和 v 之间修了两条路你从 u 到 v 选择走第一条路和选择走第二条路虽然不是同一个物理过程但在图论路径计数里它们算两条不同的路径。所以重边引发的这次额外累加恰好是题目要求统计的内容。注意如果题目明确说“重边只算一条路径”那才需要去重。但洛谷 P1144 明确允许重边并且按不同边计数所以不要把重边去掉。4.3 取模的位置别等到最后题目要求答案对 100003 取模所以每一步累加都应该及时取模。不要写一个cnt[v] cnt[u]然后想着最后输出前再统一取模。如果图里存在很多条路径cnt 的值可能早就超过 int 范围了最后取模会得到错误的溢出结果。我习惯的写法是cnt[v] (cnt[v] cnt[u]) % MOD;在第一次赋值cnt[v] cnt[u]时cnt[u] 本身已经是取模后的值所以继承下来的值也一定在合法范围内。这样整个计算过程里所有 cnt 都小于 100003完全不用担心溢出。4.4 用dist数组代替vis数组很多初学 BFS 的人会额外开一个 bool vis 数组标记节点是否已访问。在这道题里其实不需要因为你已经有了 dist。dist 初始为 -1就代表这个点还没有被计算过最短距离当你第一次访问它时dist 被赋成一个非负整数以后再遇到就只需要判断是否等距。这里有个容易犯迷糊的地方如果某个节点已经被访问过但此时又有一条边满足等距条件说明它不是第一次被发现了那么此时不应该再次入队只累加 cnt 就够了。如果你画蛇添足地把它重新入队会导致同一个点被处理多次后面的节点计数也会跟着翻倍最终答案完全不对。4.5 输入与输出性能这类百万级数据的题目输入量动辄几百万个整数。我实测过cin 如果不关闭同步基本告别 AC关闭同步后勉强能过但耗时仍然偏高。scanf 是没问题的getchar 手写快读更稳。所以我的 C 模板里直接写了快读函数。输出也不要掉以轻心。需要输出 n 行整数如果 n 是 1e6用 printf 逐行打印是可以的但要避免用 cout endl因为 endl 每次都会强制刷新缓冲区在这种数据量下是致命打击。如果你喜欢用 cout记得用\n代替 endl并且提前关闭同步。5. 从P1144延伸出去带权最短路计数与DP题单的联动5.1 带权图就用Dijkstra计数如果把边权从 1 改成任意正整数BFS 的“逐层扩展”性质就不成立了因为更长的边可能先被访问到但并不是最短路。这时候你需要换用堆优化 Dijkstra。Dijkstra 里计数的核心逻辑其实和 BFS 版本几乎一样只不过更新条件从dist[u] 1变成了dist[u] wif (dist[v] dist[u] w) { dist[v] dist[u] w; cnt[v] cnt[u]; pq.push({dist[v], v}); } else if (dist[v] dist[u] w) { cnt[v] (cnt[v] cnt[u]) % MOD; }Dijkstra 能保证每个节点第一次出队时它的距离已经确定之后不会再变小。所以当一个节点出队时所有能贡献 cnt 的前驱也都已经处理完了这时你再给它累加 cnt就不会发生“前驱还没算好”的尴尬情况。正因为这个性质Dijkstra 最短路计数是所有带权最短路计数问题的通用方案。5.2 为什么说它是一道“披着图论外衣的DP”把最短路计数抽象一下你会发现它完全符合 DP 的三个要素状态是每个点的 cnt转移方程是cnt[v] cnt[u]顺序是 dist 递增。由于最短路的性质所有点按照 dist 从小到大排成一个 DAG不存在环所以可以安全地做动态规划。这就解释了为什么有些“洛谷动态规划题单”里会收录它。很多 DP 题难的地方在于你不知道转移顺序而最短路计数里 BFS 帮你把顺序排好了你只需要专心写转移逻辑。反过来想以后再遇到“DAG 上路径计数”的题你完全可以套用这套思维先把图拓扑排序再按拓扑序做状态转移。P1144 就是一个非常好的热身。5.3 几个值得动手练的小变式如果你刷完 P1144 还想再巩固一下可以考虑下面几个方向把输出从“1 到每个点”改成“只输出 1 到 n 的最短路计数”实现上几乎零改动但能帮你确认自己有没有真正理解输出逻辑。把图改成有向图输入时只加一条方向的边重新跑一遍感受一下有向和无向在 BFS 处理上的区别。再进阶一点求出所有最短路经过的总边数这就要额外记录每个点最短路的前驱数量并做一次汇总 DP是 P1144 的一个不错延伸。这些变式都不会跑出太多新知识点但对巩固思路非常有帮助。我个人刷这题的体会是代码其实很短真正值钱的是那个 if 的判断顺序。第一次写的时候我习惯先判dist[to] dist[u] 1再判是否未访问结果起点和重边样例直接挂掉。后来我每次写图论计数题都会默念先更新未访问再累加等距。这个顺序不是行文习惯而是算法正确性的直接体现。如果你也卡在这题不要急着看更多题解把dist[u] 1和cnt[v] cnt[u]这两行想明白比背十道模板都有用。