畅通工程续：最短路径算法入门必刷题与避坑指南

很多人最初接触“最短路径”这四个字就是从“畅通工程续”这道题开始的。题目编号1874在不少刷题平台和训练单里都能看到它给出城镇数量和道路信息查询两个城镇之间的最短通行时间走不到就输出-1。看起来平平无奇但我在自己写、帮别人看代码、再到复盘这道题的过程里见过不下十种翻车方式。这篇文章就从题面出发配合两种主流解法把最短路里最容易踩的位置一个个拆开讲清楚。当前网上流传较广的版本里城镇数N一般不超过 200道路数也在千条以内城镇编号从 0 开始。这个范围设计得非常温和使得 Floyd、Dijkstra、SPFA 几种思路都能通过也正因为如此它成了很多人的最短路“入门第一题”。1. 为什么“畅通工程续”能成为最短路入门的必写题目1.1 题目在问什么先梳理一下题面。输入第一行是N和M表示城镇总数与道路总数接下来M行每行给出三个整数A B X表示城镇A到城镇B之间有一条用时为X的道路最后给你起点S和终点T要求输出从S到T的最短耗时。如果两者之间没有任何路径输出-1。这个模型就是图论里最经典的“单源最短路径”问题城镇是节点道路是边通行时间是边权目标是求起点到终点的最小权值总和。常见版本里道路是无向的也就是A到B能走B到A也能走等价的代码操作就是在邻接矩阵的对称位置都填上同一个值。如果题目改成了有向图只需要把对称赋值去掉其他逻辑不变。很多初学者一开始会被“1874”这个编号吓到觉得是不是有什么难度门槛。实际做下来会发现它的考点非常基础不涉及负权边也不涉及复杂限制踏踏实实理解一遍最短路的松弛思想就能顺利 AC。1.2 为什么新手和老手都喜欢拿它练手我总结下来有三个原因。第一数据范围小容错率高。N 200意味着哪怕用最简单、没有任何优化的O(N^2)版本 Dijkstra单组数据也毫无压力用O(N^3)的 Floyd 同样轻松跑完。这种环境对初学者极度友好算法选型不必纠结重点可以放在理解原理而不是极限优化上。第二模型足够具体。“城镇”“道路”“通行时间”都是生活化词汇比抽象术语更容易建立直觉。你不需要额外脑补一堆概念就能把题目里的人物关系翻译成邻接矩阵或邻接表。第三它考察的内容覆盖面很好。建图、初始化、松弛、访问标记、不可达判断、多组输入处理几乎最短路入门的全部知识点都在这一道题里出现。能把这道题干净利落地写对说明你的基础模板已经成型了。1.3 “畅通工程”这个题名里的延续感这套题名借用了工程背景先判断城镇之间是否连通再求最短距离。第一代“畅通工程”通常用并查集解决任务是判断整张图的连通性到了“续”路已经修了一部分下一步就是计算两地之间最短需要多久。对学习者来说这种命名方式形成了一条自然的认知链先连通再求最短路。也正因如此很多训练计划把它放在并查集题单之后、图论算法题单的开头衔接得非常舒服。2. 题目读起来简单但三处细节最容易让代码翻车2.1 重复道路不是覆盖而是取最小值这是这道题最大的一个坑。题面并没有说两个城镇之间只会出现一条道路所以同一对节点之间完全可以出现多条边例如0 1 20 0 1 15正确做法是保留15因为这代表两条可选的路线求最短距离时当然选更短的那条。但如果读入时直接graph[a][b] x后面那条20就会把15覆盖掉答案自然偏大。我见过不少人的错误代码逻辑、松弛、初始化全对就是卡在这一行。正确的读入写法是用比较更新if (x graph[a][b]) { graph[a][b] x; graph[b][a] x; }这道题给定的是无向图所以同步更新对称位置。如果题目明确说明是有向边只更新单向就好。2.2 起点等于终点答案是 0不是 -1当S T时从自己到自己不需要任何道路最短距离是0。如果你用 Dijkstra初始化dist[S] 0最后输出dist[T]自然得到0问题不大。但如果你用 Floyd就很容易踩坑忘记把dp[i][i]初始化为0矩阵对角线全部是INF那么查询自己到自己的结果就会变成-1。不要觉得这个场景太极端。实际组卷、对拍、手动测试时完全可能出现S T的情况。最稳妥的习惯是在建图阶段就统一处理for (int i 0; i N; i) { dp[i][i] 0; }不管是邻接矩阵还是邻接表版本都先把这个“自环为0”的语义写清楚后面逻辑才不会被边界条件打乱。2.3 多组测试数据与数组重置“畅通工程续”是典型的多组输入题目需要不断读入直到 EOF。每一组N M都是一次独立的子问题上一组数据留下来的graph、dist、visited都会污染下一组答案。常见错误有两个一是忘记用while (scanf(%d%d, N, M) 2)包裹主体逻辑二是只在程序开始初始化了数组却忘了每组数据开始前重新执行memset。这里我强烈建议把“数组初始化”单独封装成一个函数比如reset()每组数据读入第一行后先调用再开始处理道路。别小看这一步它能消灭掉一整个类别的 WA。2.4 无向边必须双向插入另一个看似低级但实际高频的错误只存了graph[a][b]忘记存graph[b][a]。如果题目要求是无向图而你只建了单向边那么样例可能恰好能过因为样例里的查询方向可能正好顺着你存的方向但数据一复杂就立刻翻车。最稳的写法是每次加边都写成两行赋值或者写一个addEdge函数统一处理。在邻接表版本里就是在edges[a]和edges[b]里分别插入对方的信息。反正多写一行不亏。3. Floyd 与 Dijkstra 的选型这道题两种写法都能过3.1 数据范围是最大的仁慈为什么这道题能同时容纳多种算法因为N 200。Floyd 的复杂度是O(N^3)代入后大约 800 万次循环Dijkstra 堆优化是O(M log N)在这种规模下就是毫秒级。OJ 时间限制通常给得比较宽松所以无论你写哪一种都能稳稳通过。也正因为范围小这道题并不需要你去做极限性能比较。我反而觉得它的意义在于让你把 Floyd 和 Dijkstra 都实现一遍然后仔细观察它们各自的特征和适用场景。3.2 两种算法本质差异的对比维度FloydDijkstra解决的问题任意两点之间的最短路径单源点到其他所有点的最短路径时间复杂度O(N^3)朴素 O(N^2)堆优化 O(M log N)空间占用N x N 矩阵视建图方式而定代码难度三重循环极易记忆需要理解松弛和贪心更容易出错适用场景点数少、多查询、需要任意两点距离点数多、起点固定、查询相对少负权边不支持不支持可以看到Floyd 是“全源”算法一次计算就能得到任意两点之间的答案Dijkstra 是“单源”算法一次只能解决一个起点的问题。如果题目有多次询问且每次起点不同Floyd 的处理方式就是把所有距离先全部算完然后每次查询直接查表输出Dijkstra 则要为每个起点重跑一遍。3.3 到底用哪一个从 AC 的角度我会推荐 Floyd尤其是比赛时间紧张时它写起来最短逻辑也不容易出边界问题。从学习角度Dijkstra 是每个写图论题的人都绕不开的基础建议至少手写一遍朴素O(N^2)版本再写一遍堆优化版本体会两种写法的差异。我实际带过的人里有人在“畅通工程续”这道题上直接跳过 Floyd 去学 Dijkstra结果被priority_queue的排序方向折磨了很久。反过来也有人只背了 Floyd 模板遇到N 2000的单源题就傻眼。所以更合理的学习路径是先用 Floyd 把最短路思想建立起来再用 Dijkstra 升级成单源场景的高效工具。4. Dijkstra 实现的关键细节与完整代码4.1 邻接矩阵版适合当基础模板对于N 200的题目邻接矩阵版的 Dijkstra 完全够用而且代码直白非常适合用来理解“松弛”过程。完整代码可以这样写#include cstdio #include cstring #include algorithm using namespace std; const int MAXN 205; const int INF 0x3f3f3f3f; int graph[MAXN][MAXN]; int dist[MAXN]; bool used[MAXN]; int N, M; void dijkstra(int start) { memset(dist, 0x3f, sizeof(dist)); memset(used, false, sizeof(used)); dist[start] 0; for (int cnt 0; cnt N; cnt) { int u -1; int minDist INF; for (int i 0; i N; i) { if (!used[i] dist[i] minDist) { minDist dist[i]; u i; } } if (u -1) break; // 剩余节点都不可达 used[u] true; for (int v 0; v N; v) { if (!used[v] graph[u][v] ! INF) { dist[v] min(dist[v], dist[u] graph[u][v]); } } } } int main() { while (scanf(%d%d, N, M) 2) { memset(graph, 0x3f, sizeof(graph)); for (int i 0; i N; i) { graph[i][i] 0; } for (int i 0; i M; i) { int a, b, x; scanf(%d%d%d, a, b, x); if (x graph[a][b]) { graph[a][b] x; graph[b][a] x; } } int S, T; scanf(%d%d, S, T); dijkstra(S); if (dist[T] INF) { printf(-1\n); } else { printf(%d\n, dist[T]); } } return 0; }这里的核心思想是贪心每次从“还没确定最短距离的点”里挑一个dist最小的把它当作当前确定距离然后尝试用它去更新邻居。已经标记为used的点不再参与后续更新因为它的最短距离已经确定。4.2 堆优化版本priority_queue 的两个大坑当图的点数变大朴素的O(N^2)循环就会变慢这时候需要用堆优化。核心改动是把“找最小 dist 的点”这一步交给优先队列#include bits/stdc.h using namespace std; const int MAXN 205; const int INF 0x3f3f3f3f; struct Edge { int to, cost; }; vectorEdge edges[MAXN]; int dist[MAXN]; int N, M; void dijkstra_heap(int start) { memset(dist, 0x3f, sizeof(dist)); dist[start] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push(make_pair(0, start)); while (!pq.empty()) { pairint,int cur pq.top(); pq.pop(); int d cur.first; int u cur.second; if (d ! dist[u]) continue; // 过滤过期数据 for (size_t i 0; i edges[u].size(); i) { int v edges[u][i].to; int cost edges[u][i].cost; if (dist[u] cost dist[v]) { dist[v] dist[u] cost; pq.push(make_pair(dist[v], v)); } } } }第一个坑是排序方向。C 的priority_queue默认是大根堆也就是队头是最大值。直接push(dist[v], v)是不行的取到的永远是当前最大距离的点算法会彻底乱掉。解决办法是把模板参数改成greaterpairint,int变成小根堆。如果你不想写那么长的一串类型名也可以存负数pq.push(make_pair(-dist[v], v))弹出时再取负。第二个坑是过期数据。同一个点可能因为被多次松弛而入队多次队里有旧距离和新距离两份记录。如果不对d ! dist[u]做判断旧数据弹出时会拿着一个夸大的距离继续更新邻居导致某些路径统计错误。加一行过滤看似不起眼却能避免一大堆隐蔽问题。4.3 INF 取值为什么不用 0x7fffffff很多人习惯用INT_MAX表示无穷大但在最短路代码里这是隐患。因为松弛时会执行dist[u] graph[u][v]如果两个INF级别的数相加int 直接溢出变成负数下一次比较时反而认为它更小结果把所有正常距离全部打乱。0x3f3f3f3f约等于 10 亿两个相加也不会溢出而且它有一个神奇的特性按字节memset填充后每个字节都是0x3f整个 int 正好等于0x3f3f3f3f所以memset(dist, 0x3f, sizeof(dist))非常方便。4.4 访问标记到底该在什么时候打在堆优化写法里很多人会习惯性地在pq.push时顺手把点标记成已访问。这是错误做法。原因是松弛可能多次发生你先标记了后面更短的距离就无法再更新这个点。正确的标记时机是“从堆里取出来并且确认它就是当前最短距离”的那一刻。在朴素版本里就是找到未访问点中 dist 最小的那个再把它标记为 used。5. Floyd 三重循环的正确姿势与性能实测5.1 为什么 k 必须放在最外层Floyd 只有不到十行核心代码却是初学者最容易写错顺序的算法。有人把k放在内层样例过了结果一交就 WA。原因是 Floyd 的状态定义是动态规划dp[i][j]表示“只允许经过前 k 个中间点时i 到 j 的最短路径”。这个k是阶段必须一层层扩大允许经过的点集合所以它必须是最外层循环。如果你把k放内层等于每个阶段只更新一次 i、j 的组合状态没有迭代起来答案自然不对。5.2 完整代码针对“畅通工程续”Floyd 版本的核心逻辑如下#include cstdio #include cstring #include algorithm using namespace std; const int MAXN 205; const int INF 0x3f3f3f3f; int dp[MAXN][MAXN]; int N, M; int main() { while (scanf(%d%d, N, M) 2) { memset(dp, 0x3f, sizeof(dp)); for (int i 0; i N; i) { dp[i][i] 0; } for (int i 0; i M; i) { int a, b, x; scanf(%d%d%d, a, b, x); if (x dp[a][b]) { dp[a][b] x; dp[b][a] x; } } for (int k 0; k N; k) { for (int i 0; i N; i) { if (dp[i][k] INF) continue; for (int j 0; j N; j) { if (dp[i][k] dp[k][j] dp[i][j]) { dp[i][j] dp[i][k] dp[k][j]; } } } } int S, T; scanf(%d%d, S, T); if (dp[S][T] INF) { printf(-1\n); } else { printf(%d\n, dp[S][T]); } } return 0; }这里有几个值得说的地方。首先dp[i][i] 0是必须的否则自环查询会出错。其次读入边时同样要用min逻辑处理重复道路。第三if (dp[i][k] INF) continue;是一层小剪枝跳过了明显不可达的中间点能让循环更快一点。这个剪枝不加也不影响正确性但加了会省去不少无效加法。5.3 实测与感受当N 200时三重循环大约 800 万次在普通 OJ 环境下单组数据是毫秒级。即使测试数据有几十组Floyd 也不会有压力。空间上200 x 200 的 int 矩阵只有约 160KB非常轻量。所以这道题用 Floyd 是“杀鸡用牛刀但牛刀确实好使”。我实际对比过 Floyd 和 Dijkstra 在这道题上的体验Floyd 的编码时间大约只有 Dijkstra 的三分之二调试时也很少出幺蛾子Dijkstra 则能让你把“松弛”“贪心选择”“优先队列过滤”这些概念落到实处。所以如果你想快速拿分选 Floyd 没错如果你想打牢基础Dijkstra 也请务必写一遍。6. WA 排查链路从错误提交到 AC 的完整过程6.1 一次典型 WA 的调试过程之前有个朋友贴了一份 Floyd 版本的代码给我说样例能过提交总显示答案错误。我让他做两件事第一检测S T的情况第二把dp[0][i]和dp[i][0]打印出来看看有没有异常尤其是对角线。打印结果一出问题立刻浮出水面dp[0][0]不是 0而是 1061109567也就是0x3f3f3f3f。原因就是他没有在初始化时设置dp[i][i] 0自环距离永远处于“不可达”状态。查询0 0时输出-1查询0 1时dp[0][0]没能参与松弛路径完全断掉。修复就是在建图时补上对角线的 0一组数据立刻从 WA 变成 AC。另外一次是 Dijkstra 堆优化版本表现是“答案比预期大”。我让他把每次松弛后dist数组打印出来发现某个点被旧数据更新了一次后面新数据入队后dist确实变小了但优先级队列里还留着旧的大距离记录。弹出旧记录时由于没有过滤它又把它当成有效距离去更新邻居把已经算好的值又改大了。加上if (d ! dist[u]) continue;后问题彻底消失。这个案例能很好地说明过期数据过滤不是锦上添花而是堆优化 Dijkstra 的必要组成。6.2 快速自查清单如果你也卡在 WA 里可以按下面的顺序逐条排查现象检查重点修复方法答案总是偏大重复道路读入改用min更新而不是直接赋值查询自己到自己是 -1对角线初始化设置dp[i][i] 0样例通过但某些数据不对无向边是否双向插入检查所有加边操作输出出现负数INF 采取0x7fffffff换成0x3f3f3f3f堆优化版本结果错优先队列排序方向改成小根堆或存负距离结果错乱且时好时坏多组数据未重置数组封装reset()函数每组调用这个清单其实可以复用。很多最短路题目翻车点都是同一批只不过换了层皮而已。6.3 输出答案前的统一判断无论用哪种算法最后输出前都要判断距离是否为INF。这里直接用等于判断就够if (dist[T] INF)或if (dp[S][T] INF)。不需要写 INF因为你初始化和更新逻辑里用的都是同一个常量不可达时dist[T]只可能是初始值。判断之后输出-1否则输出距离。有人会问为什么不直接把INF设成-1这样就不用判断了这个思路在输出阶段可以但算法内部的松弛比较需要极大的正数作为“未访问”的代称所以还是分开处理更规范。7. 从畅通工程到真实路网最短路能力的延伸7.1 这道题真正教会你的东西“畅通工程续”本身难度不大但它的训练价值在于把图论最基础的三板斧贯彻了一遍建图能力、松弛思想、边界处理。你以后写任何图论题都会反复遇到重复边、自环、不可达、多组输入这几个问题。能把这道题一次写对说明你的基础模板已经足够干净后面学SPFA、Bellman-Ford、A*都会扎实很多。说得再远一点生活里的导航软件计算通勤路线、网络设备选择链路、游戏角色在地图中寻路底层都是这些最短路算法。你可能不会在业务代码里手写一个 Dijkstra但理解它的贪心逻辑和边界约束能让你在面对“最短路径”类业务需求时第一时间想到应该用什么工具以及哪里会出错。7.2 下一步怎么走如果这道题已经 AC而且你能不看模板重新写出两种解法那么下一步可以沿着这个方向继续处理带负权边的图学习Bellman-Ford和SPFA处理更大规模稀疏图尝试真正在N 100000级别使用堆优化 Dijkstra处理多源多汇问题进一步理解 Floyd 的动态规划本质再进阶一点可以接触带负权且无负环的图、有向无环图上的拓扑DP以及各类变形题。强烈推荐把这些最短路模板整理成自己的代码库。每次遇到新题先套模板跑通再用数据去验证边界最后回归到原理层面看模板为什么会这样写。这个过程本身就是算法能力提升的路径。7.3 最后的小建议我在实际写题时一定会把“初始化图”和“初始化 dist / used”分开写并在每组数据开始前调用一次。这个习惯帮我躲过了无数多组输入题目的坑。如果你现在还在为了 WA 反复交题建议也试试把所有需要重置的数组变成清清爽爽的一行函数调用而不是散落在主函数的各个角落。等你写到后面的复杂图论题会庆幸自己早早就养成了这个习惯。