1. 从“最短路径”说起：一个看似简单却无处不在的问题
“最短路径”这四个字，听起来简单直白，但它几乎是所有与“连接”和“移动”相关的计算问题的核心。从我们每天使用的手机地图导航，到物流公司规划全国配送路线，再到网络路由器决定数据包的下一跳，甚至是在游戏里让角色自动寻路避开障碍物，背后都离不开最短路径算法的身影。信息学奥赛（OI）的经典教材《信息学奥赛一本通》中，将“最短路径问题”作为图论部分的核心例题，其重要性不言而喻。这道编号为1342的例题，正是初学者叩开图论与算法优化大门的一块关键敲门砖。
很多刚接触图论的同学，一看到“最短路径”，可能立刻会想到“两点之间，线段最短”的几何公理。但在计算机的世界里，尤其是在由点和边构成的“图”中，情况要复杂得多。这里的“短”不再是纯粹的物理距离，它可以是时间、成本、权重等任何可量化的代价。问题的核心在于：在一个由顶点（V）和带权边（E）构成的图中，给定一个起点和一个终点，如何找到一条从起点到终点的路径，使得这条路径上所有边的权重之和最小？这就是最短路径问题的本质。
这道例题之所以经典，是因为它剥离了复杂场景的外衣，将一个抽象的、模型化的最短路径问题直接呈现在我们面前。它不涉及动态障碍、实时交通信息，也不考虑多目标优化，就是最基础的、静态的、有权图的最短路径求解。掌握这个基础模型，就像学会了加减乘除，是后续解决所有复杂变种问题（如次短路径、第K短路径、带有负权边的最短路径等）的基石。接下来，我将结合常见的竞赛场景和实战经验，带你一步步拆解这个问题，不仅弄懂“怎么做”，更要明白“为什么这么做”，以及在实际编码和调试中会遇到哪些“坑”。
2. 问题建模：将现实抽象为图
在动手写任何代码之前，我们必须先完成最关键的一步：将问题描述抽象成计算机能够处理的图模型。这是算法竞赛和实际工程中至关重要的一环，模型建错了，后面再精巧的算法也是徒劳。
题目通常会给出一些顶点（城市、路口、网络节点等）和连接这些顶点的边（道路、线路、连接等），每条边会有一个权值（距离、时间、费用等）。我们的输入格式一般如下：首先读入顶点数n和边数m，然后依次读入m条边，每条边包含三个信息：起点u、终点v和权重w。最后，读入查询的起点s和终点t。
例如，一个简单的输入可能是：
5 7 1 2 5 1 3 2 2 3 1 2 4 3 3 4 6 3 5 4 4 5 2 1 5这表示一个有5个顶点、7条边的图。我们需要计算从顶点1到顶点5的最短路径长度。
这里有几个关键的建模细节和常见陷阱：
图的类型判断：首先需要判断这是有向图还是无向图。例题通常是无向图，意味着边(u, v, w)表示可以从u走到v，也可以从v走到u，代价都是w。在代码存储时，我们需要存储两条有向边：u->v权重w和v->u权重w。如果题目明确是有向图，则只存一条边。这是一个非常容易疏忽的点，一旦存错，结果必然错误。
权重的范围与类型：权重w的数据类型是什么？是整数还是浮点数？范围有多大？这决定了我们在代码中应该使用int还是long long，甚至是double。例如，如果权重是距离且可能为小数（如两点间欧氏距离），就必须用double。同时，权重的范围也影响了我们在初始化“最短距离数组”时“无穷大”（INF）值的设定。INF必须是一个比任何可能的最短路径总和都大的数，但又不能太大导致加法溢出。对于int类型，通常设INF = 0x3f3f3f3f，这个值大约10^9，满足大多数情况，且两个INF相加不会溢出成负数。
顶点的编号：顶点通常从1开始编号，而我们的数组习惯从0开始索引。在存储邻接表或邻接矩阵时，需要保持一致，要么全部转换为0-based索引，要么在读取和访问时进行-1操作。我个人的习惯是，在读取输入后，立即将顶点编号减1，转换为0-based索引，这样可以直接用作数组下标，不易出错。在输出时，如果需要还原为1-based编号，再加1即可。
重边和自环：图中可能存在多条连接同一对顶点的边（重边），也可能存在起点和终点相同的边（自环）。对于最短路径问题，重边我们通常只保留权重最小的那条，因为走权重大的边显然不是最优解。自环则可以直接忽略，因为走自环不会改变当前位置，只会增加路径长度。在邻接矩阵中，存储时可以用min操作来处理重边；在邻接表中，虽然可以都存下来，但在使用某些算法（如朴素Dijkstra）时，这会导致不必要的性能损耗。
完成建模后，我们就得到了一个清晰的数据结构（邻接矩阵或邻接表）来存储这个图，接下来就可以选择算法来求解了。
3. 算法选型：为什么是Dijkstra？
面对最短路径问题，我们有几个候选算法：Floyd-Warshall（多源最短路）、Bellman-Ford（带负权边）、SPFA（Bellman-Ford的队列优化）、以及Dijkstra算法。对于例题这种边权为非负数的单源最短路径问题，Dijkstra算法是公认的最优选择。
为什么是Dijkstra？我们来对比一下：
- Floyd-Warshall：计算图中所有顶点对之间的最短路径，时间复杂度为 O(n^3)。当只需要一个起点到其他点的距离时，用它就是“杀鸡用牛刀”，效率太低。
- Bellman-Ford/SPFA：能处理带有负权边的图，并检测负权环。但它们的平均时间复杂度高于Dijkstra（SPFA最坏情况也是O(VE)）。既然题目保证了边权非负，我们当然要选用在非负权图上效率更高的Dijkstra。
- Dijkstra算法：基于贪心策略，在非负权图上能保证找到最短路径。其核心思想是，将顶点分为两个集合：已确定最短距离的集合
S和未确定的集合T。每次从T中选出当前距离起点最近的顶点u，将其加入S，并用u来松弛（更新）其所有邻居顶点的距离。一旦终点被加入S，算法就可以提前结束。
Dijkstra算法有两种主流实现方式，适用于不同规模的数据：
1. 朴素版本（邻接矩阵存储）：适合稠密图（边数 m 接近 n^2），且顶点数 n 较小（通常 n <= 500）。它的时间复杂度是 O(n^2)。实现非常简单：用一个dist[]数组记录起点到各点的当前最短距离，用一个visited[]数组标记顶点是否已加入集合S。每次循环，遍历所有顶点找出未访问且dist最小的顶点u，然后遍历所有顶点，用graph[u][v]来更新dist[v]。这种方法的代码直观，易于理解和调试，是初学者必须掌握的实现。
2. 堆优化版本（邻接表存储）：适合稀疏图（边数 m 远小于 n^2），或顶点数 n 较大（n > 1000）的情况。时间复杂度为 O((m+n) log n)。它使用一个最小堆（优先队列）来高效地获取当前距离最小的顶点。我们不再需要visited数组，因为同一个顶点可能被多次加入堆，但我们只处理第一次从堆中取出的版本（此时的距离才是最短的）。这是竞赛和工程中的标配实现。
对于《一本通》的例题，通常数据规模不会特别大，两种实现都可能适用。但作为学习和练习，我强烈建议两种都亲手实现一遍。理解朴素版本能让你透彻掌握Dijkstra的贪心本质，而掌握堆优化版本则是你解决更大规模问题的必备技能。
注意：Dijkstra算法不能处理带有负权边的图！因为其贪心策略基于一个假设：“当前未访问顶点中距离最小的顶点，其距离不会再被更新”。如果存在负权边，这个假设就不成立了，因为通过后续的负权边，可能产生一条更短的路径。这是Dijkstra算法的根本局限性，务必牢记。
4. 实战编码：从朴素实现到堆优化
理论清晰了，我们开始动手写代码。我会给出两种实现的详细代码、注释，并对比它们的特点。
4.1 朴素Dijkstra实现详解
假设我们使用邻接矩阵g[N][N]存储图，dist[i]存储起点s到顶点i的最短距离，vis[i]标记顶点i是否已确定最短距离。
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1005; // 根据题目最大顶点数设定 const int INF = 0x3f3f3f3f; // 表示“无穷大” int n, m, s, t; int g[N][N]; // 邻接矩阵 int dist[N]; // 最短距离数组 bool vis[N]; // 访问标记数组 void dijkstra(int start) { // 1. 初始化 memset(dist, 0x3f, sizeof(dist)); // 所有距离初始化为无穷大 memset(vis, false, sizeof(vis)); // 所有顶点未访问 dist[start] = 0; // 起点到自己的距离为0 // 2. 循环n次，每次确定一个顶点的最短距离 for (int i = 0; i < n; ++i) { // 2.1 寻找当前未访问顶点中，dist最小的顶点u int u = -1; for (int j = 0; j < n; ++j) { if (!vis[j] && (u == -1 || dist[j] < dist[u])) { u = j; } } // 如果找不到（说明剩下的顶点不可达），可以提前结束 if (u == -1 || dist[u] == INF) break; // 2.2 标记顶点u已访问（已确定最短路径） vis[u] = true; // 2.3 用顶点u松弛其所有邻居顶点v for (int v = 0; v < n; ++v) { // 如果u和v之间有边，且通过u到v比当前已知的到v的距离更短 if (g[u][v] != INF && dist[u] + g[u][v] < dist[v]) { dist[v] = dist[u] + g[u][v]; } } } } int main() { cin >> n >> m; // 初始化邻接矩阵 memset(g, 0x3f, sizeof(g)); for (int i = 0; i < n; ++i) g[i][i] = 0; // 自己到自己的距离为0，非必需 for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; u--; v--; // 转换为0-based索引 // 无向图，存两条边。如果有重边，取最小值。 g[u][v] = min(g[u][v], w); g[v][u] = min(g[v][u], w); } cin >> s >> t; s--; t--; // 转换索引 dijkstra(s); if (dist[t] == INF) { cout << -1 << endl; // 根据题目要求，不可达输出-1或其他 } else { cout << dist[t] << endl; } return 0; }代码要点与避坑指南：
- INF的选择：
0x3f3f3f3f是一个很好的选择，因为它足够大（~1e9），且memset可以方便地用0x3f字节来填充，使得每个int都是这个值。两个INF相加也不会溢出成负数（0x3f3f3f3f * 2 < 0x7fffffff）。 - 重边处理：在读入边时，使用
g[u][v] = min(g[u][v], w);可以自动处理重边，只保留最短的边。 - 提前跳出：在寻找
u的循环后，如果u == -1或dist[u] == INF，说明剩余顶点都与起点不连通，可以提前结束算法，这是一个小的优化。 - 索引转换：在
main函数中统一进行u--, v--操作，将1-based输入转换为0-based存储，能极大减少后续代码的思维负担和出错概率。
4.2 堆优化Dijkstra实现详解
当图是稀疏图时，朴素方法O(n^2)的复杂度就不可接受了。我们需要使用邻接表存储，并用优先队列（最小堆）来优化寻找dist最小顶点的过程。
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef pair<int, int> PII; // first: 距离, second: 顶点编号 const int N = 100005; // 顶点数上限 const int M = 200005; // 边数上限（无向图要存两倍） const int INF = 0x3f3f3f3f; int n, m, s, t; int h[N], e[M], ne[M], w[M], idx; // 邻接表 int dist[N]; bool vis[N]; // 这里vis数组仍然有用，用于判断是否已确定最短距离 void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } void dijkstra(int start) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[start] = 0; priority_queue<PII, vector<PII>, greater<PII>> pq; // 最小堆 pq.push({0, start}); // 放入起点，距离为0 while (!pq.empty()) { // 3.1 取出当前距离最小的顶点 auto t = pq.top(); pq.pop(); int u = t.second; int d = t.first; // 关键！如果这个顶点已经处理过（距离已确定），则跳过 if (vis[u]) continue; // 标记为已处理 vis[u] = true; // 3.2 松弛操作：遍历u的所有出边 for (int i = h[u]; i != -1; i = ne[i]) { int v = e[i]; int new_dist = d + w[i]; if (new_dist < dist[v]) { dist[v] = new_dist; // 将新的距离和顶点放入堆中。注意：同一个v可能被多次放入堆。 pq.push({dist[v], v}); } } } } int main() { cin >> n >> m; // 初始化邻接表头指针 memset(h, -1, sizeof(h)); idx = 0; for (int i = 0; i < m; ++i) { int u, v, w_val; cin >> u >> v >> w_val; u--; v--; add(u, v, w_val); add(v, u, w_val); // 无向图 } cin >> s >> t; s--; t--; dijkstra(s); if (dist[t] == INF) { cout << -1 << endl; } else { cout << dist[t] << endl; } return 0; }堆优化版本的核心与陷阱：
vis数组的必要性：很多人认为堆优化版本不需要vis数组，这是错误的。因为同一个顶点v可能被多次加入堆（每次松弛更新距离时都会加入）。当我们从堆中取出一个顶点时，如果它的距离d大于当前dist[u]，说明这个记录是过时的，应该直接跳过。vis数组的作用就是标记该顶点是否已被确定最短距离（即第一次从堆中取出时）。一旦确定，后续所有从堆中取出的该顶点记录都可以跳过。用if (d > dist[u]) continue;也可以替代vis数组，逻辑等价。- 优先队列的定义：
priority_queue<PII, vector<PII>, greater<PII>>定义了一个最小堆，pair默认按first排序，所以我们把距离放在first，顶点编号放在second。 - 复杂度分析：每个顶点最多被加入堆一次（确定最短距离后），每条边最多引发一次松弛操作和一次入堆操作。堆操作是
O(log n)，所以总复杂度是O((m+n) log n)。对于稀疏图，这比O(n^2)快得多。 - 邻接表存储：注意无向图边的数量
m要乘以2来分配数组大小M。h数组初始化为-1很重要。
5. 路径还原：如何记录并输出具体走法？
很多时候，题目不仅要求输出最短路径的长度，还要求输出具体的路径序列。这就需要我们在算法运行过程中，记录下“最短路径树”上每个顶点的前驱节点。
原理：在松弛操作dist[v] = dist[u] + w成功执行时，意味着我们找到了一条从起点到v的更短路径，而这条路径是通过u过来的。因此，我们可以记录pre[v] = u。
我们在两种版本的Dijkstra中都可以加入一个pre数组（初始化为-1）来实现。
以堆优化版本为例，添加路径还原：
int pre[N]; // 前驱节点数组 void dijkstra(int start) { // ... 初始化部分同上 ... memset(pre, -1, sizeof(pre)); // 初始化前驱 // ... while (!pq.empty()) { // ... 取出顶点u ... if (vis[u]) continue; vis[u] = true; for (int i = h[u]; i != -1; i = ne[i]) { int v = e[i]; int new_dist = d + w[i]; if (new_dist < dist[v]) { dist[v] = new_dist; pre[v] = u; // 关键：记录v的前驱是u pq.push({dist[v], v}); } } } } // 输出从起点s到终点t的路径（逆序） void print_path(int t) { if (t == -1) return; print_path(pre[t]); // 递归先打印前驱 cout << t + 1 << " "; // 输出时转换回1-based编号 } // 在main函数中调用 if (dist[t] != INF) { cout << dist[t] << endl; print_path(t); // 输出路径 } else { cout << -1 << endl; }注意事项：
- 这样打印出来的路径是从起点到终点的顺序。因为我们是递归到起点再开始打印。
- 如果需要存储路径以便后续使用，可以将其压入一个
vector中。 - 如果存在多条最短路径，标准的Dijkstra算法只会记录其中一条（取决于松弛操作的顺序）。如果需要所有最短路径，则需要更复杂的数据结构（如
vector<int> pre[N]）来存储所有可能的前驱，并使用DFS进行回溯。
6. 边界条件与常见错误排查
即使算法原理和代码都懂了，在实际提交时仍然可能遇到各种“Wrong Answer”。下面是一些高频的坑点和排查思路：
1. 无穷大 INF 设置不当：
- 问题：
INF设置太小，导致本应不可达的点被错误地松弛。 - 检查：估算最大可能路径长度。如果有
n个顶点，最大边权为W，那么最长路径最多包含n-1条边，总长不超过(n-1)*W。INF必须大于这个值。使用0x3f3f3f3f（约1e9）对于大多数题目（n*W < 1e9）是安全的。
2. 图存储错误（有向/无向混淆）：
- 症状：样例能过，但提交后部分测试点错误。
- 排查：这是最常见错误之一。反复审题，确认图是有向还是无向。如果是无向图，代码中是否存了双向边？我习惯在注释里明确写上
// 无向图或// 有向图以提醒自己。
3. 重边未处理：
- 症状：同样样例能过，但可能在某些包含重边的测试点上出错。
- 排查：对于邻接矩阵，使用
g[u][v] = min(g[u][v], w);。对于邻接表，虽然可以存储所有重边，但在使用朴素Dijkstra时，这会导致不必要的松弛判断（虽然结果正确，但可能超时）。保险起见，可以在读入时用邻接矩阵或map暂存最小边权，最后再构建邻接表。
4. 顶点编号转换错误：
- 症状：随机出现数组越界、结果错误。
- 排查：坚持一个原则：内部存储统一使用0-based索引。在
main函数读入u, v后，立即进行u--; v--;。在输出路径时，再统一+1转换回来。这样可以避免在算法核心逻辑中混杂索引转换，降低出错率。
5. 堆优化Dijkstra中 vis 数组或距离判断遗漏：
- 症状：程序可能陷入死循环，或者结果错误（通常偏大）。
- 排查：务必记得在从堆中取出顶点后，判断
if (vis[u]) continue;或if (d > dist[u]) continue;。这是堆优化版本正确性的关键保障。
6. 数据类型溢出：
- 症状：输入较大时，结果出现负数或明显错误。
- 排查：检查所有与距离、权重相关的变量类型。如果
n*w可能超过int范围（约2e9），果断使用long long。dist数组、INF常量、中间计算结果都要换。
调试技巧：对于复杂样例，可以尝试输出中间结果。例如，在Dijkstra循环中，打印每次选中的顶点u和更新后的dist数组。与手动模拟的结果对比，能快速定位逻辑错误。
7. 性能优化与进阶思考
掌握了基础版本后，我们可以思考一些优化和进阶方向，这在解决更复杂问题时很有用。
1. 稀疏图与稠密图的自动选型： 在竞赛中，有时你无法预判数据是稠密还是稀疏。一个简单的策略是：如果m的数量级接近n^2，使用朴素Dijkstra（O(n^2)）；否则使用堆优化Dijkstra（O(m log n)）。可以写一个判断，或者直接准备两个版本的函数。
2. 使用更快的堆： C++ STL的priority_queue通常足够快。但在极端性能要求的场景下，手写二叉堆、斐波那契堆或使用std::set（可以修改元素）可能略有优势，但对于OI/ACM竞赛，priority_queue是完全够用的。
3. 多源最短路径与单源最短路径： 如果问题需要计算多个起点到多个终点的最短路径，不要对每个起点都跑一遍Dijkstra（O(k * (m log n))）。考虑： * 如果图是静态的，且查询次数k很多，可以使用Floyd-Warshall算法（O(n^3)）预处理所有点对距离，之后每次查询就是O(1)。 * 如果图是静态的，但只有少数几个源点，可以对每个源点跑一次Dijkstra，结果存下来。 * 如果图是动态的（边权会变），则需要更复杂的数据结构。
4. 输出路径的优化： 递归输出路径在路径很长时可能有栈溢出风险（尽管OI中通常不会）。可以用循环迭代的方式，先将路径节点存入数组，再逆序输出。
vector<int> path; for (int v = t; v != -1; v = pre[v]) { path.push_back(v); } reverse(path.begin(), path.end()); for (int node : path) cout << node + 1 << " ";5. 理解算法的本质与变种： Dijkstra算法本质是BFS（广度优先搜索）的加权版本。普通BFS的队列保证了“层序”遍历，而Dijkstra的优先队列保证了“按当前最短距离”的顺序遍历。理解这一点，有助于你将其思想应用到其他类似问题，例如使用“双端队列BFS（0-1 BFS）”处理边权仅为0或1的图，其时间复杂度可以降到O(V+E)。
最短路径问题是一个深不见底的领域，从经典的Dijkstra、Bellman-Ford、Floyd，到应对特殊图结构的算法（如DAG上的拓扑排序求最短路），再到用于寻路的A*算法，以及实际网络中的路由协议（如OSPF）。这道《一本通》的例题，为我们打开了这扇大门。我个人的体会是，基础算法的实现一定要做到“肌肉记忆”般熟练，同时要深刻理解其背后的图模型和贪心/动态规划思想。这样，当遇到变形题时，你才能快速识别出问题的本质，并选择或修改合适的算法来解决它。在平时练习时，不妨多找一些需要输出路径、处理重边、判断连通性、甚至边权有少量负值（需要结合SPFA判断）的变种题来做，巩固和拓展对这个知识点的掌握。
