如果你刚开始刷图论里的最短路径多半会在某个题单里看到这个题号杭电oj1874题名叫《畅通工程续》。这道题在ACM入门圈子里出场率极高很多人对Dijkstra的第一印象就是它给的。它不考复杂的建模不涉及负权边、负环、多源汇这些花活就是一个干干净净的单源最短路径问题输入输出也很规整可以说是一道少见的“什么都给你配好了”的入门题。我第一次做这道题的时候还没领悟到“重边”这个坑随手写了个邻接矩阵就直接提交结果WA到怀疑人生。后来翻了讨论区才明白题目里的“可能有多条道路”是认真的——两条城镇之间完全可以重复修路你得自己取最小值。这也是我把这道题记到现在的原因越简单的题越能让你把基础细节扎牢。这篇文章就围绕杭电oj1874展开把题意、算法选型、朴素Dijkstra、堆优化Dijkstra、Floyd三种写法全部串一遍最后再聊聊那些最常见的WA原因和调试习惯。不管你是刚接触最短路径的初学者还是想把这题当模板复习的选手这篇都能直接拿来用。1. 题目到底在考什么先把题意读懂1.1 题面翻译城镇、道路和距离题面背景很直白某个地方有N个城镇编号从0到N-1M条双向大道连接其中一些城镇每条大道有一个路程长度X。现在给你一个起点城镇S和一个终点城镇T要求输出从S到T的最短路径长度如果根本无法到达就输出-1。看起来非常简单但它把所有最短路径算法的核心要素都覆盖了带权图、无向边、单源点、单终点、可能有多个测试用例。没有负权边没有负环不需要判断路径是否存在环路问题也不需要输出具体路径方案只需要最短距离数值。这样纯净的条件正是“教科书级”最短路径题的标配。做法上也基本没有分歧Dijkstra是首选Floyd也能过数据范围不大时两者都能在1秒内跑完。这题难的不是算法本身而是你能不能把读入、初始化、边界判断这些容易被忽略的细节全部处理好。1.2 隐藏的输入输出细节读题容易忽略的点读题不仔细的话有三个点特别容易踩第一多组输入。题目说“输入包含多组测试数据”所以代码必须写成while (scanf(...) ! EOF)或者while (cin n m)只处理一组数据就退出程序的话本地样例能过一提交就是Output Limit Exceeded或者运行结果完全对不上。第二城镇编号从0开始。很多人习惯把数组下标从1开始用于是读入的城镇编号也下意识减一结果越界或者路径对不上。这题的城镇就是0到N-1直接当下标用就行。第三输出格式要求“每组输出占一行”S和T之间没有多余空格。看起来是废话但如果你在输出后面多打了一个空格遇到严格判题时也会WA。2. 选哪种最短路径算法Dijkstra还是Floyd2.1 三种可选思路对比针对这道题主流解法有三种朴素Dijkstra、堆优化Dijkstra、Floyd-Warshall。我先用一张表把它们的关键差异摆出来后面再逐个展开。算法时间复杂度代码量适用场景本题表现朴素DijkstraO(N^2)少稠密图、小数据范围稳过堆优化DijkstraO((NM)logN)中稀疏图、大数据范围稳过Floyd-WarshallO(N^3)极少多源最短路、小数据范围能过从图上来看N大概在200以内M也没有大到离谱所以理论上三种都能跑完。floyd在N200时的复杂度是800万次左右1秒内完全没压力朴素Dijkstra在N200时更是只算4万次级别可以说快得没有任何悬念。2.2 为什么说这是Dijkstra的“教科书题”Dijkstra算法的要求是图中不能有负权边因为它是基于“已确定最短距离的点不会再次被更新”这个贪心思想运行的。一旦出现负权边这条性质就被打破算法会给出错误结果。这道题的道路长度X显然是非负的天然满足Dijkstra的适用条件。同时题目是单源点求最短路径正好命中Dijkstra的典型场景。你用Floyd也能做但它会计算所有点对之间的最短距离等于多算了很多不必要的信息用Bellman-Ford也能做但每条边要反复松弛N-1轮效率上完全没必要。朴素Dijkstra在理解难度和代码量之间取得了最舒服的平衡所以绝大多数题解都会选它作为标准做法。3. 核心代码实现朴素Dijkstra邻接矩阵版3.1 初始化与数据读取邻接矩阵版的重点在于初始化要干净、重边要取最小。我们先看完整的可提交代码再按步骤拆开解释。#include cstdio #include cstring #include algorithm using namespace std; const int INF 0x3f3f3f3f; const int MAXN 205; int n, m; int g[MAXN][MAXN]; int dist[MAXN]; bool vis[MAXN]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); dist[s] 0; for (int i 0; i n; i) { int u -1; int minv INF; for (int j 0; j n; j) { if (!vis[j] dist[j] minv) { minv dist[j]; u j; } } if (u -1) break; vis[u] true; for (int v 0; v n; v) { if (!vis[v] g[u][v] ! INF dist[u] g[u][v] dist[v]) { dist[v] dist[u] g[u][v]; } } } } int main() { while (scanf(%d%d, n, m) ! EOF) { memset(g, 0x3f, sizeof(g)); for (int i 0; i m; i) { int a, b, x; scanf(%d%d%d, a, b, x); g[a][b] min(g[a][b], x); g[b][a] min(g[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; }3.2 主循环与松弛操作Dijkstra的主循环做的事情不多核心就两步找当前未访问点中距离最小的点u然后用u去松弛所有相邻点v。找最小点的过程就是代码里那个minv和u的循环。每次遍历所有点挑出未访问且dist[j]最小的那个。如果找不到未访问点u -1说明剩下的点都不可达直接跳出循环。松弛操作的内层循环里有一个很多人容易忽略的细节g[u][v] ! INF这个判断。虽然dist[u] g[u][v]在两个值都是INF时也不会超过int上限因为INF 0x3f3f3f3f两倍约为21.2亿仍在int范围内但加上这个判断可以让逻辑更清楚也避免无意义的加法。同时!vis[v]保证每个节点只会被当作终点更新一次这就是Dijkstra贪心性质的体现。3.3 为什么INF选0x3f3f3f3f很多初学的人纠结INF到底取多少。这道题里取0x3f3f3f3f是非常合适的理由有两点第一它大约等于10.6亿比任何可能的真实路径距离都大得多。即使N再大一点所有边的长度和也不会超过这个数量级。第二0x3f3f3f3f的每个字节都是0x3f所以可以直接用memset(g, 0x3f, sizeof(g))按字节填充。如果你用0x7fffffff作为INFmemset就只能填0x7f得到的其实是0x7f7f7f7f而不是0x7fffffff数值变了后续比较就全乱套。输出那里也要注意判断dist[t] INF用的是严格等于而不是大于等于某个阈值。因为只要起点和终点之间没有任何一条可达路径dist[t]就会一直保留初始化时的INF值不会在松弛过程中被改成其他“恰好很大”的数。这个逻辑不需要模糊处理等号判断完全准确。4. 进阶版本邻接表 堆优化Dijkstra4.1 什么时候需要堆优化朴素Dijkstra在N等于200时跑得飞快但如果哪天刷到类似的题N变成2000、20000朴素版O(N^2)就会开始吃力。这时候需要用优先队列堆来维护“当前距离最小的未访问点”把“每次找最小点”的O(N)降低到O(logN)。堆优化Dijkstra的整体复杂度是O((NM)logN)在稀疏图里优势特别明显。比如M只有2N级别的图朴素版要跑4亿次循环的地方堆优化版可能几百万次就搞定。4.2 优先队列的小技巧堆优化版的代码相比朴素版只是换了一个数据结构核心思想没变。这里给出一个针对本题数据的版本#include cstdio #include cstring #include vector #include queue using namespace std; const int INF 0x3f3f3f3f; const int MAXN 205; struct Edge { int to, w; }; vectorEdge adj[MAXN]; int dist[MAXN]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); dist[s] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, s}); while (!pq.empty()) { int d pq.top().first; int u pq.top().second; pq.pop(); if (d ! dist[u]) continue; for (const Edge e : adj[u]) { int v e.to; int w e.w; if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } } int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { for (int i 0; i n; i) adj[i].clear(); for (int i 0; i m; i) { int a, b, x; scanf(%d%d%d, a, b, x); adj[a].push_back({b, x}); adj[b].push_back({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; }priority_queue默认是大根堆存pair时会先比较first再比较second。用greater把它反转成小根堆后每次堆顶就是当前距离最小的点。pair的第一个元素存距离第二个元素存节点编号这个顺序不能反否则会先按节点编号排序完全失去堆优化的意义。if (d ! dist[u]) continue;这行是堆优化版的精髓专业说法叫“惰性删除”。因为同一个节点可能在更新过程中被多次压入堆中旧的记录已经失效但我们不需要手动删除堆里的元素只需要在弹出时检查当前距离和dist[u]是否一致不一致就跳过。这个技巧可以防止重复处理同一节点保证算法复杂度正确。5. 换条路走Floyd-Warshall也能做5.1 Floyd的等价写法如果你对Dijkstra还不太熟或者想顺便巩固一下多源最短路知识用Floyd也能过这道题。Floyd的思路极简枚举每个点k作为中转点看能不能通过k让i到j的距离变短。#include cstdio #include cstring #include algorithm using namespace std; const int INF 0x3f3f3f3f; const int MAXN 205; int g[MAXN][MAXN]; int main() { int n, m; while (scanf(%d%d, n, m) ! EOF) { memset(g, 0x3f, sizeof(g)); for (int i 0; i n; i) g[i][i] 0; for (int i 0; i m; i) { int a, b, x; scanf(%d%d%d, a, b, x); g[a][b] min(g[a][b], x); g[b][a] min(g[b][a], x); } for (int k 0; k n; k) { for (int i 0; i n; i) { for (int j 0; j n; j) { if (g[i][k] ! INF g[k][j] ! INF g[i][k] g[k][j] g[i][j]) { g[i][j] g[i][k] g[k][j]; } } } } int s, t; scanf(%d%d, s, t); if (g[s][t] INF) printf(-1\n); else printf(%d\n, g[s][t]); } return 0; }这里有一个必须先做的初始化g[i][i] 0。因为每个城镇到自己的距离当然是0矩阵默认全INF的话后面Floyd更新时会把自环距离算错。同时读入道路时依然要用min处理重边不能直接赋值。5.2 为什么Floyd在这种题里也够用Floyd的时间复杂度是O(N^3)听上去比Dijkstra的O(N^2)慢了一个量级但在本题数据范围内差距可以忽略。假设N最大是200三重循环最多执行800万次对现代CPU来说只要几毫秒到几十毫秒。而且Floyd有个隐藏的优势它计算的是所有点对之间的最短距离。如果题目后面再加上“多次询问任意两点之间的最短路径”Floyd只需要跑一次预处理每次查询直接查表O(1)返回反而比每次重新跑一遍Dijkstra更划算。所以在竞赛里看到“N小于300且询问次数特别多”的题第一反应不应该是Dijkstra而是Floyd。当然这道题只有一次询问用Floyd属于“杀鸡用牛刀”新手理解一下它是怎么实现“逐个中转点更新”的就够了真正比赛时还是优先Dijkstra更稳妥。6. 实战中的坑重边、自环、起终点相同6.1 重边的坑这是我这道题第一次WA的元凶。题目里并没有保证每条道路唯一两座城镇之间可能出现多条不同长度的路。如果你在读入时直接写g[a][b] x; g[b][a] x;后读入的路会覆盖先读入的路一旦先读入的是短路、后读入的是长路最短路径结果就直接偏大。正确写法是g[a][b] min(g[a][b], x);。这个细节在邻接矩阵版本里尤其关键因为矩阵每个位置只能存一个数。邻接表版本会好一些因为多条边都会保留Dijkstra在松弛时会分别比较不会算错但保留无用长边会浪费一点空间和时间。6.2 起终点相同的边界情况S等于T时结果应该是0。朴素Dijkstra和堆优化Dijkstra天然满足这一点因为dist[s] 0且不会通过任何边再更新0为负数。Floyd也一样因为初始化了g[i][i] 0。但如果你忘记初始化对角线或者某些模板里把dist初始化的循环写漏了起终点相同的测试数据就会翻车。很多题目数据里会刻意放这种边界case一旦你WA了却看不出原因可以先检查这类“想当然”的初始值问题。6.3 自环的影响自环就是某个城镇修了一条通往自己的道路。理论上这种路毫无意义因为它只会让路径变长。在读入时自环数据a b会写入g[a][a]如果刚好写入一个正数而后面没有用min初始化对角线g[a][a]就不再是0Dijkstra松弛时可能把dist[a]更新成一个错误值。解决办法有两个一是在读入前就把所有g[i][i]初始化为0二是在读入边时跳过a b的情况。个人建议两条都做反正不会影响正确性还能多一层防护。7. 常见问题与调试心得7.1 高频WA原因速查表把常见的失败原因整理成一张表提交前对着过一遍能省下很多翻讨论区的时间。问题现象可能原因修复方法样例过、提交WA重边未取min读入时用g[a][b] min(g[a][b], x)输出一个巨大数INF初始化错误使用0x3f3f3f3f并统一memset起终点相同但输出非0对角线未初始化为0初始化时让g[i][i] 0多组输入只跑了一组没用EOF循环改成while (scanf(...) ! EOF)数组越界城镇编号从0开始但数组开小MAXN设成205或更大Floyd结果偏大中转循环顺序写错k循环必须放在最外层7.2 个人调试小技巧刷题踩坑多了以后我养成了一个习惯遇到WA先从三个地方查——输入处理、INF常量、边界数据。每次顺序固定不随机翻代码效率反而更高。调试具体代码时不要只盯着最终输出可以临时打印dist数组看一下每个点到起点的距离值。比如这个题如果打印出来出现某个节点距离是0x3f3f3f3f说明它不在起点所在的连通块里如果出现某个不该是0的节点变成0多半是初始化写错了。用这种“过程性输出”定位比看最终结果瞎猜快得多。如果你有对拍条件还可以写一个暴力BFS或Floyd版本随机生成小规模数据对比两个程序的输出。这种做法在正式比赛里用不上但练习阶段对提升正确率帮助极大。8. 从这道题延伸出去最短路在真实场景还能做什么8.1 地图导航和交通规划中的最短路径学了最短路算法以后你会发现生活里到处都是它的影子。地图App从一个位置到另一个位置的路线规划本质上就是在一个巨大的带权图上跑最短路径边的权重可能是行驶时间、距离、拥堵程度等多种因素的综合值。生产环境里图的规模可能达到百万甚至千万级节点所以工程上会用到A*、双向Dijkstra、分层图等多种优化手段但核心思想依然是“每次确定一个临时最短距离最小的节点往外扩展”这套东西。物流配送的路径调度也是同样的思路。一个站点要给多个订单配送时除了距离还要考虑时间窗口、车辆载重等多种约束这时问题会变成带约束的车辆路径规划但底层仍然离不开单源最短路径的计算。8.2 后续可以继续刷的题与算法方向如果你把杭电oj1874彻底吃透了后面的学习路线可以这样安排先刷几道同类型的模板题把Dijkstra写成条件反射然后学Bellman-Ford了解负权边和负环的检测方式再学SPFA虽然它在竞赛圈口碑两极分化但理解一下队列优化的思想没有坏处。图论再深入的话还有最小生成树、拓扑排序、差分约束、网络流等方向每个方向都有对应的经典题。就我在实际做题过程中的体会来说最短路这类模板题没有太多花哨技巧真正的分水岭在于能不能把细节一次写对。重边取min、对角线初始化为0、多组数据的EOF循环、INF的选择——这四个点你做到肌肉记忆之后后面刷什么最短路径题都会顺手很多。最后再多说一句每次AC之后不要急着看下一题把自己WA的原因写下来比多刷十道题更值。