企业官网建设流程全解析

如果你刚开始刷图论里的最短路径，多半会在某个题单里看到这个题号：杭电oj1874，题名叫《畅通工程续》。这道题在ACM入门圈子里出场率极高，很多人对Dijkstra的第一印象就是它给的。它不考复杂的建模，不涉及负权边、负环、多源汇这些花活，就是一个干干净净的单源最短路径问题，输入输出也很规整，可以说是一道少见的“什么都给你配好了”的入门题。

我第一次做这道题的时候还没领悟到“重边”这个坑，随手写了个邻接矩阵就直接提交，结果WA到怀疑人生。后来翻了讨论区才明白，题目里的“可能有多条道路”是认真的——两条城镇之间完全可以重复修路，你得自己取最小值。这也是我把这道题记到现在的原因：越简单的题，越能让你把基础细节扎牢。

这篇文章就围绕杭电oj1874展开，把题意、算法选型、朴素Dijkstra、堆优化Dijkstra、Floyd三种写法全部串一遍，最后再聊聊那些最常见的WA原因和调试习惯。不管你是刚接触最短路径的初学者，还是想把这题当模板复习的选手，这篇都能直接拿来用。

1. 题目到底在考什么：先把题意读懂

1.1 题面翻译：城镇、道路和距离

题面背景很直白：某个地方有N个城镇，编号从0到N-1，M条双向大道连接其中一些城镇，每条大道有一个路程长度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还是Floyd

2.1 三种可选思路对比

针对这道题，主流解法有三种：朴素Dijkstra、堆优化Dijkstra、Floyd-Warshall。我先用一张表把它们的关键差异摆出来，后面再逐个展开。

从图上来看，N大概在200以内，M也没有大到离谱，所以理论上三种都能跑完。floyd在N=200时的复杂度是800万次左右，1秒内完全没压力；朴素Dijkstra在N=200时更是只算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作为INF，memset就只能填0x7f，得到的其实是0x7f7f7f7f而不是0x7fffffff，数值变了，后续比较就全乱套。

输出那里也要注意：判断dist[t] == INF用的是严格等于，而不是大于等于某个阈值。因为只要起点和终点之间没有任何一条可达路径，dist[t]就会一直保留初始化时的INF值，不会在松弛过程中被改成其他“恰好很大”的数。这个逻辑不需要模糊处理，等号判断完全准确。

4. 进阶版本：邻接表 + 堆优化Dijkstra

4.1 什么时候需要堆优化

朴素Dijkstra在N等于200时跑得飞快，但如果哪天刷到类似的题，N变成2000、20000，朴素版O(N^2)就会开始吃力。这时候需要用优先队列（堆）来维护“当前距离最小的未访问点”，把“每次找最小点”的O(N)降低到O(logN)。

堆优化Dijkstra的整体复杂度是O((N+M)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; }; vector<Edge> adj[MAXN]; int dist[MAXN]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); dist[s] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,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]就不再是0，Dijkstra松弛时可能把dist[a]更新成一个错误值。

解决办法有两个：一是在读入前就把所有g[i][i]初始化为0；二是在读入边时跳过a == b的情况。个人建议两条都做，反正不会影响正确性，还能多一层防护。

7. 常见问题与调试心得

7.1 高频WA原因速查表

把常见的失败原因整理成一张表，提交前对着过一遍，能省下很多翻讨论区的时间。

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的原因写下来，比多刷十道题更值。