1. 从一道题看透Dijkstra的本质
1.1 这道题到底在问什么
“最小花费”这个标题看起来平平无奇，但它几乎是每个学图论的人都会撞上的一道经典题。题目的核心场景通常是这样：给定n个点、m条边，每条边有一个“花费”权重，要求从起点到终点走哪条路总花费最小。有时候是求单点到单点，有时候是求单点到所有点，还有时候会加一点变形，比如“花费”不是简单相加而是相乘、或者有汇率转换的味道。
我第一次碰到这类题的时候，脑子里第一反应是DFS暴力枚举所有路径。结果数据范围一上来，n=1000、m=10000，直接超时到怀疑人生。后来才明白，这类“边权非负、求最短路径”的问题，就是Dijkstra算法的主场。
这道题适合谁？如果你刚学完图的存储（邻接矩阵或邻接表），想找一个能真正跑起来的练手题，那它非常合适。如果你已经写过几遍Dijkstra但总是TLE或者WA，那这篇文章里关于堆优化和边界处理的细节，应该能帮你把坑填上。
1.2 为什么是Dijkstra而不是别的
图的最短路算法有好几个，选哪个不是拍脑袋决定的。我把常见选择的逻辑整理一下：
| 算法 | 适用条件 | 时间复杂度 | 典型场景 |
|---|---|---|---|
| Dijkstra | 边权非负 | O((n+m)logn) 堆优化 | 单源最短路，边权为正 |
| Bellman-Ford | 允许负权 | O(nm) | 含负权边、判负环 |
| Floyd | 多源最短路 | O(n³) | n很小，求任意两点距离 |
| BFS | 边权全为1 | O(n+m) | 无权图或等权图 |
“最小花费”这类题，花费通常是正数（钱不可能是负的），所以Dijkstra是最优解。Bellman-Ford虽然也能做，但复杂度高一个量级，没必要。Floyd在n≤500的时候可以考虑，但n一大就废了。
注意：如果题目里出现了“花费可以为负”或者“有返现”这种描述，那Dijkstra就不能用了，必须换Bellman-Ford。这是很多人踩过的坑——看到最短路就无脑上Dijkstra，结果负权边直接让贪心策略失效。
1.3 贪心思想的生活化理解
Dijkstra的核心是贪心：每次从“还没确定的点”里挑一个当前距离最小的，把它标记为“已确定”，然后用它去更新邻居的距离。
你可以这样理解：假设你要从家去某个陌生城市，手里有一张地图，上面标了各段路的油费。你先把所有城市分成两类——“已经确定最便宜路线的”和“还没确定的”。一开始只有家是确定的，距离为0。然后你每次从没确定的城市里挑一个当前累计油费最少的，认为“到它的最便宜路线已经找到了”，再用它去修正其他城市的油费估计。
为什么这个贪心是对的？因为所有边的权重都是非负的。如果你当前到A的估计是10，到B的估计是20，那么从B绕道去A不可能更便宜——因为从B到A至少还要加一个非负的权重，只会让总花费更大。这个性质保证了“当前最小的估计值就是最终答案”。
2. 核心细节与实现要点拆解
2.1 图的存储方式怎么选
存储方式直接决定了代码的效率和写法。常见的有三种：
- 邻接矩阵：
g[i][j]表示i到j的边权。优点是写起来简单，更新和查询都是O(1)。缺点是空间O(n²)，n=10000的时候就是1亿个int，直接爆内存。只适合n≤1000的小数据。 - 邻接表（vector版）：
vector<pair<int,int>> g[n]，每个点存一个邻居列表。空间O(n+m)，适合稀疏图。写起来也不复杂，是我最常用的方式。 - 链式前向星：用数组模拟链表，
head[]、nxt[]、to[]、w[]四个数组。空间最省，速度最快，但写起来稍微绕一点。竞赛里常用，日常练习用vector就够了。
“最小花费”这类题，m通常远小于n²，所以邻接表是首选。我一般直接写：
vector<pair<int,int>> g[MAXN]; // g[u] = {v, w}2.2 朴素版Dijkstra的完整逻辑
朴素版的时间复杂度是O(n²)，适合n≤1000的情况。核心步骤：
- 初始化
dist[]数组为无穷大，dist[start]=0。 - 用一个
visited[]数组标记已确定的点。 - 循环n次：每次找一个未访问且dist最小的点u，标记visited[u]=true；然后遍历u的所有邻居v，如果
dist[u]+w < dist[v]，就更新dist[v]。
这里有个细节很多人会写错：找最小dist的点时，如果找不到（dist为无穷大），说明剩下的点都不可达，可以直接break。不加这个判断虽然不会错，但会多跑一些无用的循环。
void dijkstra(int start, int n) { for (int i = 1; i <= n; i++) dist[i] = INF; dist[start] = 0; memset(visited, 0, sizeof(visited)); for (int i = 1; i <= n; i++) { int u = -1, minD = INF; for (int j = 1; j <= n; j++) { if (!visited[j] && dist[j] < minD) { minD = dist[j]; u = j; } } if (u == -1) break; visited[u] = true; for (auto [v, w] : g[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; } } } }2.3 堆优化版的关键改动
朴素版每次找最小点要O(n)，总共O(n²)。用优先队列（小根堆）可以把这一步降到O(logn)，整体复杂度变成O((n+m)logn)。
改动只有两处：一是用priority_queue维护(dist, node)对，每次直接取堆顶；二是需要处理“过期”的堆元素——因为同一个点可能被多次入堆，如果取出来的dist比当前记录的dist大，说明是旧数据，直接跳过。
void dijkstra(int start, int n) { for (int i = 1; i <= n; i++) dist[i] = INF; dist[start] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // 过期元素，跳过 for (auto [v, w] : g[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } }提示：
greater<>让优先队列变成小根堆。默认的priority_queue是大根堆，取出来的是最大值，那就完全反了。这个点我见过太多人写错。
2.4 无穷大的选取有讲究
INF不能随便设。如果设成INT_MAX，那么dist[u]+w就可能溢出变成负数，导致更新逻辑出错。常见做法是设成0x3f3f3f3f，这个值大约是10亿，两个相加不会溢出int，而且足够大，能表示“不可达”。
const int INF = 0x3f3f3f3f;如果你用的是long long，可以设成0x3f3f3f3f3f3f3f3f。这个技巧在竞赛圈里几乎是标配，新手很容易忽略。
3. 完整实操过程与代码实现
3.1 题目建模：把“花费”翻译成图
假设题目描述是这样的：有n个城市，m条道路，每条道路有一个过路费。求从城市1到城市n的最小总花费。
建模过程：
- 城市 → 图的节点，编号1到n。
- 道路 → 图的边，无向边就存两次，有向边存一次。
- 过路费 → 边的权重w。
- 起点 → 节点1，终点 → 节点n。
如果题目问的是“从起点到所有点的最小花费”，那就输出整个dist数组。如果只问终点，就输出dist[n]。
3.2 输入处理与建图
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const int INF = 0x3f3f3f3f; vector<pair<int,int>> g[MAXN]; int dist[MAXN]; int main() { int n, m, s, t; cin >> n >> m >> s >> t; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); // 无向图 } // Dijkstra memset(dist, 0x3f, sizeof(dist)); dist[s] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto [v, w] : g[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } if (dist[t] == INF) cout << -1 << endl; else cout << dist[t] << endl; return 0; }这段代码可以直接抄去用。注意几个点：无向图要存两次边；输出前判断是否可达；memset按字节赋值，0x3f每个字节都是0x3f，所以整个int就是0x3f3f3f3f。
3.3 手动模拟一遍执行过程
用一个具体例子走一遍，加深理解。假设有4个点，5条边：
1 --2-- 2 1 --5-- 3 2 --1-- 3 2 --3-- 4 3 --2-- 4求1到4的最小花费。
初始化：dist = [0, INF, INF, INF]（下标从1开始）。
第一轮：取点1，dist=0。更新邻居：dist[2]=2，dist[3]=5。堆里有(2,2)、(5,3)。
第二轮：取点2，dist=2。更新邻居：到3，2+1=3 < 5，dist[3]=3；到4，2+3=5，dist[4]=5。堆里有(3,3)、(5,3旧)、(5,4)。
第三轮：取点3，dist=3。更新邻居：到4，3+2=5，不小于dist[4]=5，不更新。堆里有(5,3旧)、(5,4)。
第四轮：取点3（旧的，dist=5 > 当前dist[3]=3），跳过。取点4，dist=5，结束。
最终dist[4]=5，路径是1→2→4，花费2+3=5。也可以走1→2→3→4，花费2+1+2=5，一样。但1→3→4是5+2=7，更贵。
这个手动模拟能帮你确认代码逻辑是否正确。如果你写的代码跑出来不是5，那就对照这个流程找问题。
3.4 复杂度分析与数据范围匹配
| 数据范围 | 推荐写法 | 复杂度 |
|---|---|---|
| n≤1000, m≤10000 | 邻接矩阵+朴素Dijkstra | O(n²) |
| n≤10^5, m≤2×10^5 | 邻接表+堆优化 | O((n+m)logn) |
| n≤10^5, m≤2×10^5, 多组查询 | 堆优化+预处理 | 视情况 |
“最小花费”这类题，如果n到了10^5级别，朴素版必超时。我实测过，n=10000、m=50000的时候，朴素版跑一次大概0.3秒，堆优化版只要0.01秒。差距非常明显。
4. 常见问题与排查技巧实录
4.1 为什么我的答案总是比正确答案大
这是最常见的问题。原因通常有三个：
- 忘记处理重边：两个点之间可能有多条边，你只存了最后一条。解决办法是存边的时候不覆盖，或者取最小值。用邻接表存所有边就不会有这个问题，因为Dijkstra会自动选最小的那条。
- INF设得太小：如果路径总花费超过了INF，就会被误判为不可达。检查一下INF是否大于所有可能路径的最大值。
- 无向图只存了一次边：题目说“道路”通常是双向的，只存u→v不存v→u，会导致某些点不可达。
4.2 堆优化版为什么会TLE
堆优化版TLE通常是因为堆里元素太多。每次更新都push一个新元素，最坏情况下堆的大小是O(m)。如果m=10^6，堆操作就会很慢。
优化技巧：可以用pair的默认比较，但要注意greater<>的写法。另外，如果同一个点的dist被多次更新，可以只保留最新的，但标准做法就是push后跳过过期元素，这个开销是可以接受的。
还有一种情况是用了cin/cout没关同步。数据量大的时候，cin比scanf慢很多。加上这两行：
ios::sync_with_stdio(false); cin.tie(0);4.3 常见问题速查表
| 现象 | 可能原因 | 排查方法 |
|---|---|---|
| 答案偏大 | 重边未处理、INF太小 | 打印dist数组逐点检查 |
| 答案偏小 | 有负权边、更新条件写反 | 确认边权非负、检查<方向 |
| 部分点不可达 | 无向图只存单向、起点编号错 | 检查建图代码、确认起点 |
| TLE | 用了朴素版、cin未关同步 | 换堆优化、加sync_with_stdio |
| 段错误 | 数组开小、越界访问 | 检查MAXN是否够大 |
| 死循环 | 优先队列比较器写错 | 确认是小根堆 |
4.4 几个容易忽略的边界情况
- 起点等于终点：dist[s]=0，直接输出0。代码里不需要特判，因为初始化就是0。
- 图不连通：终点不可达时输出-1或题目指定的值。不要直接输出INF。
- 只有一个点：m=0，循环不执行，dist[s]=0，正确。
- 自环：u到u的边，权重非负，不会影响结果，但会浪费一次更新。可以忽略。
注意：有些题目会问“最小花费”但边权是乘法关系（比如汇率转换）。这时候Dijkstra的贪心策略需要调整——因为乘法下“当前最小”不一定保证全局最优，除非所有边权都大于1。遇到这种变形题要特别小心，最好先确认边权性质。
4.5 我踩过的三个坑
第一个坑是memset(dist, 0x3f, sizeof(dist))写成了memset(dist, INF, sizeof(dist))。memset是按字节赋值的，INF=0x3f3f3f3f有四个字节，memset只会取最低字节0x3f，结果每个int变成0x3f3f3f3f，看起来对了，但如果INF定义成别的值就会出错。正确写法是memset(dist, 0x3f, sizeof(dist))。
第二个坑是优先队列的比较器。priority_queue<pair<int,int>>默认按first从大到小排，取出来的是最大值。必须写成greater<pair<int,int>>才是小根堆。我有一次忘了加，结果跑出来完全不对，调试了半小时才发现。
第三个坑是重边处理。有一次我用邻接矩阵存图，读入边的时候直接g[u][v]=w，结果后面的边覆盖了前面的。如果后面的边权重更大，就会漏掉更优的解。后来改成g[u][v]=min(g[u][v], w)才过。
5. 从这道题延伸出去的知识点
5.1 记录路径怎么改
有时候题目不只问最小花费，还要输出走的哪条路。只需要加一个pre[]数组，在更新dist的时候记录前驱节点：
if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pre[v] = u; pq.push({dist[v], v}); }最后从终点往回倒推，就能得到完整路径。注意如果有多条最短路，记录的是其中一条，具体哪条取决于更新顺序。
5.2 多源最短路怎么处理
如果题目问“从任意一个起点出发到终点的最小花费”，可以加一个虚拟源点，把它到所有起点的边权设为0，然后从虚拟源点跑一次Dijkstra。这个技巧在“最小花费”的变形题里很常见。
5.3 边权是二维的怎么办
有些题目的“花费”包含两个维度，比如时间和金钱。如果要求“在时间不超过T的前提下花费最小”，那就不是纯Dijkstra能解决的了，需要用到分层图或者带约束的最短路。这种题一般会出现在进阶训练里，基础阶段先把一维的练熟。
5.4 和最小生成树的区别
新手容易把最短路和最小生成树搞混。最短路是“从起点到终点的一条路径”，最小生成树是“连接所有点的一棵树”。前者用Dijkstra，后者用Kruskal或Prim。虽然都涉及“最小”，但目标完全不同。判断方法很简单：如果题目问“从A到B怎么走最省”，是最短路；如果问“把所有点连起来最少花多少”，是最小生成树。
我在实际写题的时候，一般会先把Dijkstra的模板默写一遍，确认没有笔误再开始改。模板这种东西，写熟了就是肌肉记忆，但隔一段时间不写就容易在细节上翻车。建议你也准备一份自己的模板，每次写之前对照检查一遍关键点：INF的值、优先队列的比较器、过期元素的跳过、无向图的双向存边。这四个地方不出错，基本就能AC。
