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

很多人最初接触“最短路径”这四个字，就是从“畅通工程续”这道题开始的。题目编号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 两种算法本质差异的对比

可以看到，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; }; vector<Edge> edges[MAXN]; int dist[MAXN]; int N, M; void dijkstra_heap(int start) { memset(dist, 0x3f, sizeof(dist)); dist[start] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push(make_pair(0, start)); while (!pq.empty()) { pair<int,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)是不行的，取到的永远是当前最大距离的点，算法会彻底乱掉。解决办法是把模板参数改成greater<pair<int,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 里，可以按下面的顺序逐条排查：

这个清单其实可以复用。很多最短路题目翻车点都是同一批，只不过换了层皮而已。

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 反复交题，建议也试试：把所有需要重置的数组变成清清爽爽的一行函数调用，而不是散落在主函数的各个角落。等你写到后面的复杂图论题，会庆幸自己早早就养成了这个习惯。