如果你刷过洛谷的图论题单大概率会在某个晚上和 P1144 重逢。这道题全名叫“最短路计数”题面短得让人以为是道水题实际上它是从“会写 BFS”到“会用 BFS 解决问题”之间的一道典型门槛。P1144 给你一张 N 个点、M 条边的无向无权图每条边长度都是 1要求从 1 号点出发输出到每个点的最短路条数答案对 100003 取模。数据范围可以达到 N10^6 级别M2×10^6 级别这意味着算法必须是线性的。对刚开始刷题的人来说这道题最大的价值在于逼你理解 BFS 的分层扩展顺序并且把“求最短距离”和“统计最短路径条数”这两件事同时做对。不管你是刚学图论的新手还是准备参加算法竞赛的老手我都建议把这道题独立写一遍值得。1. 项目概述P1144 是什么题为什么值得认真做一遍1.1 题目还原与核心需求题面说得很简洁给出一张无向连通图也不排除多个连通分量的写法反正只从 1 号点出发每条边的长度为 1。换句话说这是一张无权图。要求从 1 号点出发到每个点的最短路径分别有多少条。拆开来看这里面其实有两个需求求出每个点到 1 号点的最短路长度统计出最短路条数。第二个需求才是关键。很多同学学 BFS 的时候只会用队列求“最少步数”一遇到“计数”就懵了不知道在哪一步做加法。P1144 正好把这个问题摆到台面上你要在 BFS 逐层扩展的过程中维护一个方案数数组并且保证每个点的方案数被完整累加。题目编号是 P1144在洛谷的图论题单里属于“最短路”板块的入门题。但从实际刷题反馈来看它挺有分量的。能不看题解写出来的人说明对 BFS 的理解已经进阶了写不出来的往往是对“什么时候更新 dist、什么时候更新 cnt”这两个判断条件不够清楚。1.2 这道题到底在考什么P1144 的标签是“最短路”“BFS”但真正拉开差距的是三个细节。第一是“无权图”这个前提。因为边权全为 1BFS 第一次访问到某个点时距离一定是最短的。这一点和带权图不同带权图必须用 Dijkstra因为第一次弹出的点未必是最短路。理解了这一点你才算明白为什么 BFS 能处理这题。第二是“计数”的语义。图中允许有重边。也就是说如果点 u 和点 v 之间有两条边那么从 1 到 v 的某条路径如果最后一段经过 u因为边不同应该算两条不同的最短路。这就要求在存图时保留重边在 BFS 时按每条边独立处理。第三是取模。答案数量级可能非常大在完全图或接近完全图的结构中路径数会指数级增长。题目给的模数是 100003一个很特殊的质数。它要求你在累加过程中及时取模而不是最后一次性取模。如果这三个细节没想透直接把模板背下来代码照着写也不是不能过但换个题目条件就废了。我一直觉得这种题不怕慢就怕假装懂了。2. 思路拆解为什么边权为 1 时 BFS 就是最短路算法2.1 从无权图的特殊性说起在无权图里一条路径的长度就是经过的边数。所以求最短路长度实际上就是求“最少经过几条边能到达某个点”。这正好落在 BFS 的射程内。BFS 的核心是用队列维护一个“逐层扩展”的顺序先访问起点也就是第 0 层再访问所有与起点直接相连的点也就是第 1 层然后访问第 1 层所有点向外扩展的点也就是第 2 层依此类推。因为每一层的点数可能很多但层数一定是严格递增的所以当一个点第一次被访问到时它所在的层数就是它到起点的最短距离。用一个生活化的类比把 1 号点当成消息源每个单位时间消息能沿着一条边传递给相邻的人。第一轮收到消息的人离消息源距离为 1第二轮收到消息的人距离为 2。如果你问“某人最早第几轮收到消息”那自然就是 BFS 逐层传播的过程。因为每条边耗时相同所以先到的那个人一定是最近的这就是 BFS 能求最短路的全部原因。2.2 计数问题的核心最短路树上的层序累加距离好求但条数怎么数关键在这里如果 y 是 x 的相邻点并且 dist[y] 恰好等于 dist[x] 1那么所有从起点到 x 的最短路都可以在后面接上一条边走到 y从而构成一条从起点到 y 的最短路。所以 y 的最短路条数需要累加上 x 的最短路条数。这个过程可以看成在“最短路树”上做加法。dist 数组会把图切成一层一层每个点只需要关注它在“上一层”的前驱。一个点可能有多个前驱例如起点 1 可以直接连到点 3点 2 也可以连到点 3且 dist[2]1 也等于 dist[3]那么点 3 的方案数就是 cnt[1] cnt[2] 的总和。这里有一个容易想错的地方一个点也可能通过同一个前驱的不同边到达。比如点 u 和点 v 之间有两条平行边那么从 u 走到 v 就算两条路径因为你走的是不同的边。只要你的邻接表保留了重边BFS 遍历时会分别访问这两条边所以自然会把 cnt[u] 累加两次。这是重边要求保留的原因。所以 BFS 中不能只用一个 bool 数组表示“访问过没有”而是要区分两种状态尚未访问过此时 dist[v] -1第一次到达cnt[v] cnt[u]已经访问过但 dist[v] dist[u] 1说明又找到一条最短路径cnt[v] cnt[u]。如果你用 visited 数组把第二种状态直接跳过那么所有经过相同长度的其他前驱产生的路径都会被丢掉计数就少了。2.3 为什么不用 Dijkstra / SPFA有同学可能会问Dijkstra 也能求最短路为什么 P1144 不直接用 Dijkstra因为没必要而且更慢。Dijkstra 需要维护优先队列每次取出最小值都要 O(log V)复杂度是 O((VE) log V)。对于 P1144 这种 V 和 E 都很大的题虽然也能过但代码量更大还要处理一个点可能被多次更新的问题。在无权图上BFS 天然按照距离分层队列访问顺序本身就保证了距离单调完全不需要优先队列。SPFA 就更不推荐了。SPFA 的最坏时间复杂度是 O(VE)在很多卡数据的 OJ 上会被直接打爆。P1144 的 N 是 10^6 级别M 是 2×10^6 级别SPFA 在这种数据下绝对跑不动。哪怕是随机数据能过也只是走了运。所以 P1144 的正确解法就是 BFS 加计数数组时间复杂度 O(NM)空间也是线性的。这也体现了算法选择的一个核心原则根据数据范围和问题特性选择最简单且足够快的算法。3. 代码实现与关键细节3.1 存图方式的选择vector 还是链式前向星写代码之前先得解决存图。P1144 的 N 上限是 10^6用邻接矩阵必然内存爆炸。只能用邻接表。两种常见方案vector 邻接表vector graph[N1]每个点存一个动态数组实现简单代码可读性好链式前向星用 head、to、next 三个数组手动模拟链表内存紧凑是竞赛选手的常规选择。从空间角度看vector 在 64 位环境下每个 vector 对象本身就要占约 24 字节N10^6 时光 vector 头就约 24MB再加上 2M 条边数据内存会到 40MB 以上。链式前向星则紧凑得多head 数组约 4MBto 和 next 数组各约 8MB2M 条边 × 4 字节加上 dist 和 cnt 各约 4MB总内存明显更小。从编码角度vector 确实更好写。但从长期刷题来看链式前向星是竞赛必备技能很多题解都默认用它。我个人的建议是如果你只是过 P1144vector 足够如果你想真正吃透图论算法两种都要会写。下面我用链式前向星给出完整实现因为这种写法在后续的各种图论题里都能复用。3.2 完整 C 实现#include bits/stdc.h using namespace std; const int MAXN 1000005; const int MAXM 2000005; const int MOD 100003; struct Edge { int to, next; } e[MAXM * 2]; int head[MAXN], tot; int dist[MAXN], cnt[MAXN]; void addEdge(int u, int v) { e[tot].to v; e[tot].next head[u]; head[u] tot; } int main() { int n, m; scanf(%d%d, n, m); memset(head, -1, sizeof(head)); for (int i 0; i m; i) { int u, v; scanf(%d%d, u, v); addEdge(u, v); addEdge(v, u); } memset(dist, -1, sizeof(dist)); dist[1] 0; cnt[1] 1; queueint q; q.push(1); while (!q.empty()) { int u q.front(); q.pop(); for (int i head[u]; i ! -1; i e[i].next) { int v e[i].to; if (dist[v] -1) { dist[v] dist[u] 1; cnt[v] cnt[u]; q.push(v); } else if (dist[v] dist[u] 1) { cnt[v] cnt[u]; if (cnt[v] MOD) cnt[v] - MOD; } } } for (int i 1; i n; i) { printf(%d\n, cnt[i] % MOD); } return 0; }这段代码里有几个必须强调的点。第一head 初始化为 -1目的是让遍历邻接表时能判断链表结束。用 0 作为空指针也可以但那样 to、next 数组的下标就要从 1 开始并且初始化时把 next 设为 0。两种写法都能跑我个人习惯用 -1 加 memset。第二cnt[1] 必须初始化为 1。起点到自身的方案数是 1因为“不动”也是一条长度为 0 的路径。忘了这一句整张图的计数全都会变成 0这是最常见的低级错误。第三在等距累加的分支中cnt[u] 的值在 BFS 过程中只会被更新到它自己的层数全部处理完毕之后才稳定。但由于 BFS 按照 dist 递增处理任何一个点的所有前驱它们的 dist 一定比它小所以它们一定比这个点更早出队。也就是说当我们处理后来的点时它的 cnt 已经累加完毕。这就是为什么可以直接用 cnt[u] 去更新邻接点。3.3 Java 与 Python 版本要点如果你用 Java最大的坑是输入输出。Scanner 和 System.out.println 在 10^6 级别的数据下会超时得很难看。正确做法是BufferedReader br new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw new BufferedWriter(new OutputStreamWriter(System.out));读的时候用 StringTokenizer 或 split写的时候把答案拼到一个 String 里一次输出。Java 的邻接表可以用 ArrayList []也可以用数组模拟链式前向星。如果担心性能用链式前向星更稳但 ArrayList 在这种数据规模下通常也能过。Python 版本要特别小心。P1144 的数据规模对 Python 来说并不友好直接用 list 当队列会死人要用 collections.deque。输入要用sys.stdin.buffer.read().split()一次性读入不要一行行 readline否则时间会卡在 IO 上。下面给一个参考实现import sys from collections import deque MOD 100003 data list(map(int, sys.stdin.buffer.read().split())) n, m data[0], data[1] graph [[] for _ in range(n 1)] idx 2 for _ in range(m): u, v data[idx], data[idx 1] idx 2 graph[u].append(v) graph[v].append(u) dist [-1] * (n 1) cnt [0] * (n 1) dist[1] 0 cnt[1] 1 q deque([1]) while q: u q.popleft() du dist[u] cu cnt[u] for v in graph[u]: if dist[v] -1: dist[v] du 1 cnt[v] cu q.append(v) elif dist[v] du 1: cnt[v] (cnt[v] cu) % MOD sys.stdout.write(\n.join(str(cnt[i] % MOD) for i in range(1, n 1)))这里把du dist[u]和cu cnt[u]存成局部变量是为了减少数组访问次数也让逻辑更清晰。在 Python 里局部变量的访问速度明显快于列表下标访问这种微优化在大数据下可能决定能不能在一秒内跑完。3.4 取模的正确打开方式题目模数是 100003不是常见的 1e97。这个数字看起来小但足以应对题目数据因为 P1144 的答案只要求在取模后的范围内输出。关键在于取模发生在什么时候。如果你只在最后输出前对 cnt[i] 取模中间用 long long 保存在 N10^6 级别时是扛不住的。路径数可能达到指数级long long 也会溢出。所以必须“边加边模”。C 代码里我用了一个小技巧cnt[v] cnt[u]; if (cnt[v] MOD) cnt[v] - MOD;因为 cnt[u] 和 cnt[v] 一定都在 [0, MOD-1] 范围内两者相加最大是 2*MOD-2用一次减法就能把结果拉回合法范围不需要做取模运算。这个优化虽小但在图很大的时候能省下不少时间。注意这个技巧只在“每次只加一个小于 MOD 的数”时有效。如果你在一个分支里连续加多个数那要谨慎可能加两次后就超过 2*MOD 了。那时候就要改成取模或者每加一次判断一次。P1144 里每个 v 只会被多个不同前驱分别累加但每次累加都是一次独立的加法所以这个技巧安全。4. 实操过程与踩坑记录4.1 我在实际提交过程中遇到的坑第一题坑是真的隐蔽链式前向星数组开小。无向图每条边要存成两条有向边但很多人只开了 M 大小的数组结果 M 一大的时候不一定会立刻报 RE而是覆盖了 dist 或 cnt 数组的内存导致结果莫名其妙。这个问题在用 vector 时不会出现因为 vector 会自动扩容但链式前向星必须手动分配2 * M 5空间。我做题时习惯把 MAXM 开到2000005再乘 2所以 e 数组要开到MAXM * 2。第二个坑是 BFS 的等距累加被漏掉。有人写代码时会把邻接点 v 的状态只分成“没访问过”和“访问过”然后对访问过的点一律跳过。这在普通 BFS 里没问题但在计数 BFS 里会丢路径。比如 1 连 2 和 32 和 3 都连 4且 dist[2]1 dist[3]1 dist[4]那么 4 的计数应该等于 cnt[2] cnt[3]。如果因为 2 先处理过 4等 3 处理 4 时把 3 跳过那 cnt[4] 就少算了。所以一定不能用 bool visited而要用 dist 的数值关系判断。第三个坑是初始状态不对。有人只写了dist[1] 0忘了cnt[1] 1。结果整个 cnt 数组全部保持默认 0最后输出全是 0。这种错很低级但在熬夜刷题时会让人怀疑人生。我建议在写完 BFS 后手动跑一跑题目的样例看能不能输出正确结果。4.2 常见错误速查表为了方便排错我把这一题常见的错误特征、原因和解决方案整理成一张表。症状可能原因解决办法输出全是 0cnt[1] 没有设置为 1在 BFS 前加cnt[1] 1输出偏大重边没有被正确处理把同一条路径算了两遍检查邻接表是否保留了所有重边如果是链式前向星要确认 addEdge 被调用两次输出偏小用 visited 数组跳过了等距访问的邻接点改成用 dist[v] 与 dist[u]1 的关系判断数组越界或 RE链式前向星只开了 M 空间忘记无向图要 2M数组开到2 * M 5时间超限使用邻接矩阵或 SPFA改用邻接表 BFSMOD 后结果不对中间结果溢出只在最后取模每次累加后立即取模或做减法这张表基本覆盖了新手在 P1144 上会遇到的所有问题。如果你提交后 WA先对着表自查一遍通常能快速定位。4.3 关于数据规模与空间的注意事项P1144 的数据是 N 和 M 都可以到 10^6 级别。这意味着两件事。第一图上所有边都要保留。如果是跳过重边或者合并重边答案会变少因为题目中的“两条不同的边”算两条不同的路径。合并重边只会在“不考虑边差异”的计数题里用P1144 里不能这么做。第二复杂度必须是 O(NM)。BFS 对每条边访问一次无向图相当于每条边被访问两次总体是线性。任何 O(NM) 或 O(N^2) 的做法都过不了。再提一下内存。链式前向星的四个数组headN1 个 int、to2M 个 int、next2M 个 int、dist 和 cnt各 N1 个 int。加起来大约是4 8 8 4 4 28MB再加上队列等辅助空间总内存可控。vector 版本会多一些但在 P1144 的内存限制下通常也能过。如果题目内存限制只有 128MB 甚至更低链式前向星会更稳。5. 从 P1144 延伸开去一类“最短路 计数”题型的通用套路5.1 变体一带权图最短路计数P1144 是边权为 1 的最短路计数但如果边权不同呢这时候不能直接用 BFS因为 BFS 的“逐层扩展”只有在边权相同时才等价于“按距离递增扩展”。带权图的最短路计数应该用 Dijkstra 加计数 DP。核心规则很简单当dist[v] dist[u] w时说明找到了一条更短的路那么cnt[v] cnt[u]当dist[v] dist[u] w时说明找到了一条同样长的路那么cnt[v] cnt[u]。但这里有一个坑在堆优化 Dijkstra 中一个点可能会被多次松弛甚至在它已经被弹出并标记处理后又被另一个点更新方案数。如果处理不当cnt 会重复累加。安全做法是用一个vis数组标记“已经作为中间节点扩展过”的点。弹出时如果 vis 为 true 就跳过否则标记 vis 并且扩展邻接点。然后每次松弛时都做计数更新。这样能保证每个点只被当作中间点使用一次而 cnt 的累加则发生在所有松弛操作中。这个套路在很多“最短路方案数”题里都会出现例如“恰好 K 条边的最短路计数”“最短路 次短路计数”等变体。理解了 Dijkstra 计数就掌握了一整类题的基础。5.2 变体二迷宫/网格图计数类问题另一类常见场景是网格图比如从左上角走到右下角只能上下左右走求最短路径条数。网格图和普通无向图在本质上没有区别每个格子是一个点相邻格子之间有边边权和 P1144 一样都是 1。所以 BFS 计数可以直接平移过来只要把 dist 和 cnt 改成二维数组然后从起点向四个方向扩展即可。但网格题有额外的陷阱边界条件出界判断不能少障碍物障碍格不能进入cnt 保持 0起点和终点的处理如果起点就是终点方案数是 1。这些问题虽然看似简单但如果不小心很容易在递归或 DFS 变体中出现重复搜索。P1144 的 BFS 计数框架是解决网格最短路计数的通用模板值得反复练习。5.3 变体三拓扑序上的计数 DP从 P1144 再往外走一步你会碰到一类更通用的题目在有向无环图 DAG 上统计从起点到每个点的路径数。这类题不用“最短路”的概念因为 DAG 里的任意路径长度可以不同但计数逻辑和 P1144 极其相似。区别在于DAG 需要先用拓扑排序确定一个线性顺序然后按拓扑序做 DP把前驱的方案数累加到后继上。把 BFS 计数和拓扑序计数放在一起看你会发现它们有个共同的内核在某个良序层序或拓扑序上让每个点的状态只从它的前驱转移过来。P1144 的 BFS 是最短路图层序拓扑排序是依赖层序。把这两个模型吃透很多图论 DP 题的转移顺序就自然明白了。这也是为什么洛谷动态规划题单里会出现一些图论题因为图上的计数 DP 和线性 DP 在本质上是一家人。5.4 建议的练习路线如果你已经独立 AC 了 P1144接下来可以按这个顺序往下练先做一道迷宫最短路计数题把 BFS 计数的二维数组版写一遍再做一道带权图最短路计数题熟悉 Dijkstra 加计数 DP 的写法然后是 DAG 上的路径计数 DP理解拓扑序的用法有余力再接触树上最短路计数结合 LCA 或树上差分一起练。我见过不少同学刷完 P1144 就急着去啃网络流结果基础没打牢后面看到图论题全都虚。说实话把“图 计数”这一组组合练扎实性价比非常高。它既锻炼了你对图遍历顺序的理解也锻炼了 DP 的状态设计能力是竞赛里最容易拉开分差的分水岭。我个人在带新手时会让他们用 C、Java、Python 各写一遍 P1144。每一种语言都会暴露出不同的问题C 考验数组边界和取模习惯Java 考验 IO 效率Python 考验数据结构选择。三遍写完才算真正把这道题吃透。最后分享一个我一直保留的小习惯在本地调试时把 BFS 每个节点首次入队时的 dist 和 cnt 打印出来对照样例数据走一遍。你能很直观地看到计数是怎么一层层累加的也能一眼发现等距累加漏在哪。这个调试方法对以后所有的“最短路径方案数”“路径计数”题目都管用强烈建议养成。 P1144最短路计数：从BFS到路径计数DP的图论经典题
如果你刷过洛谷的图论题单大概率会在某个晚上和 P1144 重逢。这道题全名叫“最短路计数”题面短得让人以为是道水题实际上它是从“会写 BFS”到“会用 BFS 解决问题”之间的一道典型门槛。P1144 给你一张 N 个点、M 条边的无向无权图每条边长度都是 1要求从 1 号点出发输出到每个点的最短路条数答案对 100003 取模。数据范围可以达到 N10^6 级别M2×10^6 级别这意味着算法必须是线性的。对刚开始刷题的人来说这道题最大的价值在于逼你理解 BFS 的分层扩展顺序并且把“求最短距离”和“统计最短路径条数”这两件事同时做对。不管你是刚学图论的新手还是准备参加算法竞赛的老手我都建议把这道题独立写一遍值得。1. 项目概述P1144 是什么题为什么值得认真做一遍1.1 题目还原与核心需求题面说得很简洁给出一张无向连通图也不排除多个连通分量的写法反正只从 1 号点出发每条边的长度为 1。换句话说这是一张无权图。要求从 1 号点出发到每个点的最短路径分别有多少条。拆开来看这里面其实有两个需求求出每个点到 1 号点的最短路长度统计出最短路条数。第二个需求才是关键。很多同学学 BFS 的时候只会用队列求“最少步数”一遇到“计数”就懵了不知道在哪一步做加法。P1144 正好把这个问题摆到台面上你要在 BFS 逐层扩展的过程中维护一个方案数数组并且保证每个点的方案数被完整累加。题目编号是 P1144在洛谷的图论题单里属于“最短路”板块的入门题。但从实际刷题反馈来看它挺有分量的。能不看题解写出来的人说明对 BFS 的理解已经进阶了写不出来的往往是对“什么时候更新 dist、什么时候更新 cnt”这两个判断条件不够清楚。1.2 这道题到底在考什么P1144 的标签是“最短路”“BFS”但真正拉开差距的是三个细节。第一是“无权图”这个前提。因为边权全为 1BFS 第一次访问到某个点时距离一定是最短的。这一点和带权图不同带权图必须用 Dijkstra因为第一次弹出的点未必是最短路。理解了这一点你才算明白为什么 BFS 能处理这题。第二是“计数”的语义。图中允许有重边。也就是说如果点 u 和点 v 之间有两条边那么从 1 到 v 的某条路径如果最后一段经过 u因为边不同应该算两条不同的最短路。这就要求在存图时保留重边在 BFS 时按每条边独立处理。第三是取模。答案数量级可能非常大在完全图或接近完全图的结构中路径数会指数级增长。题目给的模数是 100003一个很特殊的质数。它要求你在累加过程中及时取模而不是最后一次性取模。如果这三个细节没想透直接把模板背下来代码照着写也不是不能过但换个题目条件就废了。我一直觉得这种题不怕慢就怕假装懂了。2. 思路拆解为什么边权为 1 时 BFS 就是最短路算法2.1 从无权图的特殊性说起在无权图里一条路径的长度就是经过的边数。所以求最短路长度实际上就是求“最少经过几条边能到达某个点”。这正好落在 BFS 的射程内。BFS 的核心是用队列维护一个“逐层扩展”的顺序先访问起点也就是第 0 层再访问所有与起点直接相连的点也就是第 1 层然后访问第 1 层所有点向外扩展的点也就是第 2 层依此类推。因为每一层的点数可能很多但层数一定是严格递增的所以当一个点第一次被访问到时它所在的层数就是它到起点的最短距离。用一个生活化的类比把 1 号点当成消息源每个单位时间消息能沿着一条边传递给相邻的人。第一轮收到消息的人离消息源距离为 1第二轮收到消息的人距离为 2。如果你问“某人最早第几轮收到消息”那自然就是 BFS 逐层传播的过程。因为每条边耗时相同所以先到的那个人一定是最近的这就是 BFS 能求最短路的全部原因。2.2 计数问题的核心最短路树上的层序累加距离好求但条数怎么数关键在这里如果 y 是 x 的相邻点并且 dist[y] 恰好等于 dist[x] 1那么所有从起点到 x 的最短路都可以在后面接上一条边走到 y从而构成一条从起点到 y 的最短路。所以 y 的最短路条数需要累加上 x 的最短路条数。这个过程可以看成在“最短路树”上做加法。dist 数组会把图切成一层一层每个点只需要关注它在“上一层”的前驱。一个点可能有多个前驱例如起点 1 可以直接连到点 3点 2 也可以连到点 3且 dist[2]1 也等于 dist[3]那么点 3 的方案数就是 cnt[1] cnt[2] 的总和。这里有一个容易想错的地方一个点也可能通过同一个前驱的不同边到达。比如点 u 和点 v 之间有两条平行边那么从 u 走到 v 就算两条路径因为你走的是不同的边。只要你的邻接表保留了重边BFS 遍历时会分别访问这两条边所以自然会把 cnt[u] 累加两次。这是重边要求保留的原因。所以 BFS 中不能只用一个 bool 数组表示“访问过没有”而是要区分两种状态尚未访问过此时 dist[v] -1第一次到达cnt[v] cnt[u]已经访问过但 dist[v] dist[u] 1说明又找到一条最短路径cnt[v] cnt[u]。如果你用 visited 数组把第二种状态直接跳过那么所有经过相同长度的其他前驱产生的路径都会被丢掉计数就少了。2.3 为什么不用 Dijkstra / SPFA有同学可能会问Dijkstra 也能求最短路为什么 P1144 不直接用 Dijkstra因为没必要而且更慢。Dijkstra 需要维护优先队列每次取出最小值都要 O(log V)复杂度是 O((VE) log V)。对于 P1144 这种 V 和 E 都很大的题虽然也能过但代码量更大还要处理一个点可能被多次更新的问题。在无权图上BFS 天然按照距离分层队列访问顺序本身就保证了距离单调完全不需要优先队列。SPFA 就更不推荐了。SPFA 的最坏时间复杂度是 O(VE)在很多卡数据的 OJ 上会被直接打爆。P1144 的 N 是 10^6 级别M 是 2×10^6 级别SPFA 在这种数据下绝对跑不动。哪怕是随机数据能过也只是走了运。所以 P1144 的正确解法就是 BFS 加计数数组时间复杂度 O(NM)空间也是线性的。这也体现了算法选择的一个核心原则根据数据范围和问题特性选择最简单且足够快的算法。3. 代码实现与关键细节3.1 存图方式的选择vector 还是链式前向星写代码之前先得解决存图。P1144 的 N 上限是 10^6用邻接矩阵必然内存爆炸。只能用邻接表。两种常见方案vector 邻接表vector graph[N1]每个点存一个动态数组实现简单代码可读性好链式前向星用 head、to、next 三个数组手动模拟链表内存紧凑是竞赛选手的常规选择。从空间角度看vector 在 64 位环境下每个 vector 对象本身就要占约 24 字节N10^6 时光 vector 头就约 24MB再加上 2M 条边数据内存会到 40MB 以上。链式前向星则紧凑得多head 数组约 4MBto 和 next 数组各约 8MB2M 条边 × 4 字节加上 dist 和 cnt 各约 4MB总内存明显更小。从编码角度vector 确实更好写。但从长期刷题来看链式前向星是竞赛必备技能很多题解都默认用它。我个人的建议是如果你只是过 P1144vector 足够如果你想真正吃透图论算法两种都要会写。下面我用链式前向星给出完整实现因为这种写法在后续的各种图论题里都能复用。3.2 完整 C 实现#include bits/stdc.h using namespace std; const int MAXN 1000005; const int MAXM 2000005; const int MOD 100003; struct Edge { int to, next; } e[MAXM * 2]; int head[MAXN], tot; int dist[MAXN], cnt[MAXN]; void addEdge(int u, int v) { e[tot].to v; e[tot].next head[u]; head[u] tot; } int main() { int n, m; scanf(%d%d, n, m); memset(head, -1, sizeof(head)); for (int i 0; i m; i) { int u, v; scanf(%d%d, u, v); addEdge(u, v); addEdge(v, u); } memset(dist, -1, sizeof(dist)); dist[1] 0; cnt[1] 1; queueint q; q.push(1); while (!q.empty()) { int u q.front(); q.pop(); for (int i head[u]; i ! -1; i e[i].next) { int v e[i].to; if (dist[v] -1) { dist[v] dist[u] 1; cnt[v] cnt[u]; q.push(v); } else if (dist[v] dist[u] 1) { cnt[v] cnt[u]; if (cnt[v] MOD) cnt[v] - MOD; } } } for (int i 1; i n; i) { printf(%d\n, cnt[i] % MOD); } return 0; }这段代码里有几个必须强调的点。第一head 初始化为 -1目的是让遍历邻接表时能判断链表结束。用 0 作为空指针也可以但那样 to、next 数组的下标就要从 1 开始并且初始化时把 next 设为 0。两种写法都能跑我个人习惯用 -1 加 memset。第二cnt[1] 必须初始化为 1。起点到自身的方案数是 1因为“不动”也是一条长度为 0 的路径。忘了这一句整张图的计数全都会变成 0这是最常见的低级错误。第三在等距累加的分支中cnt[u] 的值在 BFS 过程中只会被更新到它自己的层数全部处理完毕之后才稳定。但由于 BFS 按照 dist 递增处理任何一个点的所有前驱它们的 dist 一定比它小所以它们一定比这个点更早出队。也就是说当我们处理后来的点时它的 cnt 已经累加完毕。这就是为什么可以直接用 cnt[u] 去更新邻接点。3.3 Java 与 Python 版本要点如果你用 Java最大的坑是输入输出。Scanner 和 System.out.println 在 10^6 级别的数据下会超时得很难看。正确做法是BufferedReader br new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw new BufferedWriter(new OutputStreamWriter(System.out));读的时候用 StringTokenizer 或 split写的时候把答案拼到一个 String 里一次输出。Java 的邻接表可以用 ArrayList []也可以用数组模拟链式前向星。如果担心性能用链式前向星更稳但 ArrayList 在这种数据规模下通常也能过。Python 版本要特别小心。P1144 的数据规模对 Python 来说并不友好直接用 list 当队列会死人要用 collections.deque。输入要用sys.stdin.buffer.read().split()一次性读入不要一行行 readline否则时间会卡在 IO 上。下面给一个参考实现import sys from collections import deque MOD 100003 data list(map(int, sys.stdin.buffer.read().split())) n, m data[0], data[1] graph [[] for _ in range(n 1)] idx 2 for _ in range(m): u, v data[idx], data[idx 1] idx 2 graph[u].append(v) graph[v].append(u) dist [-1] * (n 1) cnt [0] * (n 1) dist[1] 0 cnt[1] 1 q deque([1]) while q: u q.popleft() du dist[u] cu cnt[u] for v in graph[u]: if dist[v] -1: dist[v] du 1 cnt[v] cu q.append(v) elif dist[v] du 1: cnt[v] (cnt[v] cu) % MOD sys.stdout.write(\n.join(str(cnt[i] % MOD) for i in range(1, n 1)))这里把du dist[u]和cu cnt[u]存成局部变量是为了减少数组访问次数也让逻辑更清晰。在 Python 里局部变量的访问速度明显快于列表下标访问这种微优化在大数据下可能决定能不能在一秒内跑完。3.4 取模的正确打开方式题目模数是 100003不是常见的 1e97。这个数字看起来小但足以应对题目数据因为 P1144 的答案只要求在取模后的范围内输出。关键在于取模发生在什么时候。如果你只在最后输出前对 cnt[i] 取模中间用 long long 保存在 N10^6 级别时是扛不住的。路径数可能达到指数级long long 也会溢出。所以必须“边加边模”。C 代码里我用了一个小技巧cnt[v] cnt[u]; if (cnt[v] MOD) cnt[v] - MOD;因为 cnt[u] 和 cnt[v] 一定都在 [0, MOD-1] 范围内两者相加最大是 2*MOD-2用一次减法就能把结果拉回合法范围不需要做取模运算。这个优化虽小但在图很大的时候能省下不少时间。注意这个技巧只在“每次只加一个小于 MOD 的数”时有效。如果你在一个分支里连续加多个数那要谨慎可能加两次后就超过 2*MOD 了。那时候就要改成取模或者每加一次判断一次。P1144 里每个 v 只会被多个不同前驱分别累加但每次累加都是一次独立的加法所以这个技巧安全。4. 实操过程与踩坑记录4.1 我在实际提交过程中遇到的坑第一题坑是真的隐蔽链式前向星数组开小。无向图每条边要存成两条有向边但很多人只开了 M 大小的数组结果 M 一大的时候不一定会立刻报 RE而是覆盖了 dist 或 cnt 数组的内存导致结果莫名其妙。这个问题在用 vector 时不会出现因为 vector 会自动扩容但链式前向星必须手动分配2 * M 5空间。我做题时习惯把 MAXM 开到2000005再乘 2所以 e 数组要开到MAXM * 2。第二个坑是 BFS 的等距累加被漏掉。有人写代码时会把邻接点 v 的状态只分成“没访问过”和“访问过”然后对访问过的点一律跳过。这在普通 BFS 里没问题但在计数 BFS 里会丢路径。比如 1 连 2 和 32 和 3 都连 4且 dist[2]1 dist[3]1 dist[4]那么 4 的计数应该等于 cnt[2] cnt[3]。如果因为 2 先处理过 4等 3 处理 4 时把 3 跳过那 cnt[4] 就少算了。所以一定不能用 bool visited而要用 dist 的数值关系判断。第三个坑是初始状态不对。有人只写了dist[1] 0忘了cnt[1] 1。结果整个 cnt 数组全部保持默认 0最后输出全是 0。这种错很低级但在熬夜刷题时会让人怀疑人生。我建议在写完 BFS 后手动跑一跑题目的样例看能不能输出正确结果。4.2 常见错误速查表为了方便排错我把这一题常见的错误特征、原因和解决方案整理成一张表。症状可能原因解决办法输出全是 0cnt[1] 没有设置为 1在 BFS 前加cnt[1] 1输出偏大重边没有被正确处理把同一条路径算了两遍检查邻接表是否保留了所有重边如果是链式前向星要确认 addEdge 被调用两次输出偏小用 visited 数组跳过了等距访问的邻接点改成用 dist[v] 与 dist[u]1 的关系判断数组越界或 RE链式前向星只开了 M 空间忘记无向图要 2M数组开到2 * M 5时间超限使用邻接矩阵或 SPFA改用邻接表 BFSMOD 后结果不对中间结果溢出只在最后取模每次累加后立即取模或做减法这张表基本覆盖了新手在 P1144 上会遇到的所有问题。如果你提交后 WA先对着表自查一遍通常能快速定位。4.3 关于数据规模与空间的注意事项P1144 的数据是 N 和 M 都可以到 10^6 级别。这意味着两件事。第一图上所有边都要保留。如果是跳过重边或者合并重边答案会变少因为题目中的“两条不同的边”算两条不同的路径。合并重边只会在“不考虑边差异”的计数题里用P1144 里不能这么做。第二复杂度必须是 O(NM)。BFS 对每条边访问一次无向图相当于每条边被访问两次总体是线性。任何 O(NM) 或 O(N^2) 的做法都过不了。再提一下内存。链式前向星的四个数组headN1 个 int、to2M 个 int、next2M 个 int、dist 和 cnt各 N1 个 int。加起来大约是4 8 8 4 4 28MB再加上队列等辅助空间总内存可控。vector 版本会多一些但在 P1144 的内存限制下通常也能过。如果题目内存限制只有 128MB 甚至更低链式前向星会更稳。5. 从 P1144 延伸开去一类“最短路 计数”题型的通用套路5.1 变体一带权图最短路计数P1144 是边权为 1 的最短路计数但如果边权不同呢这时候不能直接用 BFS因为 BFS 的“逐层扩展”只有在边权相同时才等价于“按距离递增扩展”。带权图的最短路计数应该用 Dijkstra 加计数 DP。核心规则很简单当dist[v] dist[u] w时说明找到了一条更短的路那么cnt[v] cnt[u]当dist[v] dist[u] w时说明找到了一条同样长的路那么cnt[v] cnt[u]。但这里有一个坑在堆优化 Dijkstra 中一个点可能会被多次松弛甚至在它已经被弹出并标记处理后又被另一个点更新方案数。如果处理不当cnt 会重复累加。安全做法是用一个vis数组标记“已经作为中间节点扩展过”的点。弹出时如果 vis 为 true 就跳过否则标记 vis 并且扩展邻接点。然后每次松弛时都做计数更新。这样能保证每个点只被当作中间点使用一次而 cnt 的累加则发生在所有松弛操作中。这个套路在很多“最短路方案数”题里都会出现例如“恰好 K 条边的最短路计数”“最短路 次短路计数”等变体。理解了 Dijkstra 计数就掌握了一整类题的基础。5.2 变体二迷宫/网格图计数类问题另一类常见场景是网格图比如从左上角走到右下角只能上下左右走求最短路径条数。网格图和普通无向图在本质上没有区别每个格子是一个点相邻格子之间有边边权和 P1144 一样都是 1。所以 BFS 计数可以直接平移过来只要把 dist 和 cnt 改成二维数组然后从起点向四个方向扩展即可。但网格题有额外的陷阱边界条件出界判断不能少障碍物障碍格不能进入cnt 保持 0起点和终点的处理如果起点就是终点方案数是 1。这些问题虽然看似简单但如果不小心很容易在递归或 DFS 变体中出现重复搜索。P1144 的 BFS 计数框架是解决网格最短路计数的通用模板值得反复练习。5.3 变体三拓扑序上的计数 DP从 P1144 再往外走一步你会碰到一类更通用的题目在有向无环图 DAG 上统计从起点到每个点的路径数。这类题不用“最短路”的概念因为 DAG 里的任意路径长度可以不同但计数逻辑和 P1144 极其相似。区别在于DAG 需要先用拓扑排序确定一个线性顺序然后按拓扑序做 DP把前驱的方案数累加到后继上。把 BFS 计数和拓扑序计数放在一起看你会发现它们有个共同的内核在某个良序层序或拓扑序上让每个点的状态只从它的前驱转移过来。P1144 的 BFS 是最短路图层序拓扑排序是依赖层序。把这两个模型吃透很多图论 DP 题的转移顺序就自然明白了。这也是为什么洛谷动态规划题单里会出现一些图论题因为图上的计数 DP 和线性 DP 在本质上是一家人。5.4 建议的练习路线如果你已经独立 AC 了 P1144接下来可以按这个顺序往下练先做一道迷宫最短路计数题把 BFS 计数的二维数组版写一遍再做一道带权图最短路计数题熟悉 Dijkstra 加计数 DP 的写法然后是 DAG 上的路径计数 DP理解拓扑序的用法有余力再接触树上最短路计数结合 LCA 或树上差分一起练。我见过不少同学刷完 P1144 就急着去啃网络流结果基础没打牢后面看到图论题全都虚。说实话把“图 计数”这一组组合练扎实性价比非常高。它既锻炼了你对图遍历顺序的理解也锻炼了 DP 的状态设计能力是竞赛里最容易拉开分差的分水岭。我个人在带新手时会让他们用 C、Java、Python 各写一遍 P1144。每一种语言都会暴露出不同的问题C 考验数组边界和取模习惯Java 考验 IO 效率Python 考验数据结构选择。三遍写完才算真正把这道题吃透。最后分享一个我一直保留的小习惯在本地调试时把 BFS 每个节点首次入队时的 dist 和 cnt 打印出来对照样例数据走一遍。你能很直观地看到计数是怎么一层层累加的也能一眼发现等距累加漏在哪。这个调试方法对以后所有的“最短路径方案数”“路径计数”题目都管用强烈建议养成。