1. 题目拆解与算法选型1.1 题目到底在考什么“热浪(heatwv)”这道题在信息学奥赛一本通里是P1379如果我没记错的话位置在第八章图论算法的“最短路径”那一节紧跟在Dijkstra算法的例题组里是一道非常典型的正权图单源最短路入门题。题目本身的故事背景很直观德克萨斯州遭遇了一股热浪你所在的城市和另外一个城市之间有若干条公路连接每条公路的通行时间不同现在要求你从出发城市赶到目标城市的最短时间。把这个问题翻译成图论语言就是——给定一张N个点M条边的无向连通图边权为正求从起点s到终点t的最短路径长度。你可能觉得这道题看起来平平无奇但它被放在一本通里作为Dijkstra算法训练题是有讲究的。它考察的点其实非常清晰你会不会针对题目的数据范围选择合适的最短路算法你会不会写邻接表/链式前向星的存图方式你会不会用优先队列优化Dijkstra的常规模板你会不会处理无向边在存图时“加两条有向边”的细节你的初始化与松弛操作有没有写对。这些点和五年前考试的时候相比没什么变化今天依然是OI入门选手必须趟过去的一关。所以别急着刷下一题这道题值得你把每一行代码掰开揉碎弄明白。1.2 数据范围决定算法选择做题第一步永远不是写代码而是看数据范围。我记得一本通里这道题的N不超过2500M不超过6200边权都是正整数且规模不大。这个数据范围是比较友好的但它恰好位于“朴素Dijkstra能过但不太轻松”和“堆优化Dijkstra稳如泰山”的临界区域附近。用朴素Dijkstra也就是O(N^2)的写法在这个数据量下其实也能过因为2500的平方大概是六百多万次操作对于C在1秒时限内依然可以接受。但这里有个问题如果你习惯了朴素写法遇到N到达10万、20万的题就会立刻抓瞎。所以我的建议非常明确——直接学堆优化Dijkstra也就是O((NM)logN)的版本一步到位。这道题就是你练习堆优化写法最好的靶场。至于SPFA虽然也能过这道题但我不建议在正权图上使用。原因后面会在常见问题里细说这里先给个结论见正权图最短路默认堆优化Dijkstra不要给自己留用SPFA偷懒的毛病。1.3 为什么这道题值得反复写很多选手刷题喜欢追求数量但这道题我建议你至少独立写三遍。第一遍照着模板敲第二遍不看任何资料默写第三遍尝试加入不同的存图方式和手写堆。为什么这道题基本涵盖了图论最短路里最重要的基本功。存图方式选不好后面所有图论题都会束手束脚优先队列写不熟练很多贪心类题目也会受影响。热浪的代码量大概在六七十行不长不短恰好适合反复锤炼。我记得当年学这道题的时候第一次用邻接矩阵写了一遍然后又用vector邻接表写了一遍最后才上手链式前向星。三种存图方式各跑一遍之后对Dijkstra的理解才算真正扎实了。你可以在后面参考我给的实现但更希望你自己独立写完一遍再回来看效果完全不同。2. Dijkstra算法核心原理解读2.1 贪心思想的直观理解Dijkstra算法的本质是贪心不理解贪心就记不住模板。我用一个特别生活化的方式给你讲明白。想象你在学校操场中央要去操场另一头的商店买东西操场上有很多岔路你不知道哪条路最近。你手上有一个记录本和一个标记笔记录本上写着每个路口距离你当前出发点的最短估计距离一开始只有起点是0其他都是无穷大。算法做的事其实非常“笨”每次在所有还没确定最短距离的路口中挑一个当前记录距离最小的认为这个路口的最终最短距离已经确定了然后用这个路口去更新它旁边所有路口的记录距离如果经过这个路口能更近的话。重复这个过程直到所有路口都被标记。关键就在于“每次挑当前距离最小的出来”这个动作这就是贪心。为什么敢这么挑因为你已经选出来的点它的距离是通过一些比它更近的点更新过的而这些更近的点都已经确定最终距离了所以这个“最小距离”不可能再被其他路径更新得更小。严格证明依赖边权非负——如果边权是负数后面可能出现一条负边把曾经确定的距离改小贪心就失效了。用这个操场的比喻你再回看代码每一行都能对上号。2.2 各步骤的时间复杂度为什么这样朴素Dijkstra找最小点的过程是每次都扫描一遍所有未标记节点复杂度是O(N^2)。N很小没事N一大就成了瓶颈。堆优化Dijkstra的核心就是用一个优先队列小根堆来维护“当前距离最小的未确定点”让找最小点的动作从O(N)变成O(logN)。每条边最多被松弛一次所以总复杂度是O(MlogN)空间上多维护一个堆是O(N)。这道题M小于N的三倍左右用堆优化的优势还不太明显但你已经能感受到“每条边只会被拿出来更新一次”的简洁逻辑。等以后遇到M很大、N也大的图这个优势会放大得非常明显。2.3 边权非负为什么如此关键我刚才反复强调边权非负是因为Dijkstra的整个正确性建立在“已经确定距离的点不可能再被其他未确定的点更新得更短”这个前提上。而负权边专治这种自信。举个例子假设一条边权是-100的边连接起点和一个远方的点只通过这条负边远方点的距离立刻变成-90而它的“估算距离”比起点到其他邻居都小得多。如果算法此时把这个远方点当作确定点后面就算有别的路径把它更新得更小也已经来不及了。这个点一错后面全是错的。所以在看这道题的时候你一定留意到题目并没有负边所有道路的通行时间都是正整数。这就是命题人在告诉你——放心大胆用Dijkstra我故意没给你设负权坑。但也正因为很多题都靠这个特点送分你更要养成看题目条件的好习惯考试时先检查边权正负再决定算法。3. 完整代码与核心细节实现3.1 链式前向星存图写法先给出我推荐的完整代码使用的是链式前向星存图。这是OI竞赛里综合效率最稳妥的存图方式内存紧凑遍历速度快写熟了之后很多图论题都能通用。#include bits/stdc.h using namespace std; const int MAXN 2500 5; const int MAXM 6200 * 2 5; const int INF 0x3f3f3f3f; struct Edge { int to, w, next; } edge[MAXM]; int head[MAXN], tot; int dist[MAXN]; bool vis[MAXN]; void addEdge(int u, int v, int w) { edge[tot].to v; edge[tot].w w; edge[tot].next head[u]; head[u] tot; } struct Node { int id, d; bool operator(const Node other) const { return d other.d; // 小根堆 } }; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] 0; priority_queueNode pq; pq.push({s, 0}); while (!pq.empty()) { Node cur pq.top(); pq.pop(); int u cur.id; if (vis[u]) continue; vis[u] true; for (int i head[u]; i ! -1; i edge[i].next) { int v edge[i].to; int w edge[i].w; if (!vis[v] dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({v, dist[v]}); } } } } int main() { int n, m, s, t; memset(head, -1, sizeof(head)); cin n m s t; for (int i 0; i m; i) { int u, v, w; cin u v w; addEdge(u, v, w); addEdge(v, u, w); } dijkstra(s); cout dist[t] endl; return 0; }这个模板是我改了很多版之后稳定使用的版本有几个细节你考试时也照这样写基本不会翻车。edge数组大小开成MAXM * 2是因为无向边要存两遍宁多勿少。INF用0x3f3f3f3f是一个技巧它的十进制是1061109567足够大而且memset可以直接按字节初始化成这个值不用循环赋值。priority_queue默认是大根堆所以要重载让比较逻辑反过来或者用greaterNode哪种顺眼用哪种。最核心的if (vis[u]) continue是因为同一个点可能被多次压入堆中不跳过会白做很多无效松弛。3.2 为什么每次出堆都要判重堆优化Dijkstra有一个非常经典的细节——一个点可能被加入优先队列很多次但真正被确定最短距离、用来更新邻居的次数只有一次。为什么每次松弛操作发现距离能变小就把新的状态压入堆中所以同一个点可能以不同距离出现好几次。堆中距离最小的那次出堆就是这个点的最终最短距离。此后如果又轮到同一个点出堆但此时它的距离一定比之前那次大说明它已经被确定过了直接跳过即可。这个判重操作就是vis数组存在的原因。如果不判每个点每次出堆都会去扫描它所有的邻居复杂度会退化成接近O(MN)后果不堪设想。所以vis不是可有可无的装饰是性能的保命符。另一种常见写法是不用vis出堆时判断cur.d ! dist[u]不等就跳过。两种写法等价选一种自己习惯的、不容易记混的就好。我习惯用vis数组因为语义清楚调试时一看就知道哪些点确定了。3.3 初始化边长数组的隐患存图之前要把head数组全部初始化为-1这个操作很多新手会忘记。如果用邻接表存图这个细节直接决定你的遍历对不对。我见过有人用是0来初始化head然后addEdge里面edge[i].next head[u]这样第一个边指向0循环边界就出问题。所以建议直接约定head数组初始化为-1遍历时用i ! -1做终止条件。还有一个隐患是如果你的题目给了重边——同一对城市之间有多条道路时间不同你的addEdge天然支持存储多条边但如果你用的是邻接矩阵存图就必须在输入时取最小值。热浪这道题我没记错的话不卡重边但养成处理重边的习惯是好的后面很多图论题都会遇到。3.4 无向图存边的正确姿势题目明确说公路是双向的也就是说你可以从A城市到B城市也能从B城市到A城市。所以在addEdge时一定要调两次函数把两条相反方向的边都存进去。很多选手第一次写这道题栽在这里只加了一条方向的边结果输出永远是INF怎么调都不对。半天的调试时间就这么浪费了。我建议在main函数里加边部分固定写成一个注释标记的头每次看到就提醒自己“这是无向图要调两次”。如果你的addEdge函数写的是按引用改head和tot那加边的顺序没有影响。唯一要求是两条边都要加。4. 两种模板写法对比与选型建议4.1 vector邻接表的实现除了链式前向星vector邻接表可能是平时刷题更常见的写法因为写起来更直观。我也给你一个可以直接用的版本#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 2500 5; struct Node { int v, w; }; vectorNode g[MAXN]; int dist[MAXN]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto cur pq.top(); pq.pop(); int d cur.first, u cur.second; if (d ! dist[u]) continue; for (auto e : g[u]) { int v e.v, w e.w; if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } } 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(s); cout dist[t] endl; return 0; }这里用的是priority_queuepairint,int, vectorpairint,int, greaterpairint,intpair排序时先比first也就是距离再比second也就是节点编号逻辑完全符合需求。判重用了d ! dist[u]效果和vis一样。vector写法在热浪这种小数据上完全够用代码也更易读适合平时练习和写模板题。缺点是动态开辟内存需要频繁push性能略低于静态数组的链式前向星但数据量小时差距微乎其微。4.2 链式前向星的优势与适用场景我最终更推荐链式前向星原因有三点第一静态数组分配好内存之后不再动态申请在极端大数据的图论题里更稳第二遍历边时通过next指针跳转cache局部性更好一些实测在百万级边的时候有优势第三很多进阶图论算法如网络流、费用流也要用链式前向星存残余网络提前练熟等于一步到位。但链式前向星对新手确实不太友好看起来就是一个链表的数组实现调试时看不清楚。所以我不建议新手一上来就用它——先用vector把算法逻辑打通再回头用链式前向星优化。两个版本都跑一遍热浪你再感受一下哪个细节容易出错这比直接背一个模板更有价值。4.3 邻接矩阵为什么不该用回到热浪这道题N最大2500如果开邻接矩阵就需要2500×2500个int大概25MB内存其实还是能扛得住的。所以我见过不少初学者用邻接矩阵写这道题也过了但我不建议你这么做。邻接矩阵最大的问题是它只能存一条边遇到重边必须手动取最小值同时遍历时O(N^2)扫描无法跳过不存在的边。如果这道题的N改成10万邻接矩阵直接内存爆炸。你需要养成一个习惯看到图论题先看N范围再决定存图方式。一般来说N大于5000就该毫不犹豫放弃邻接矩阵。5. 常见问题排查与避坑心得5.1 输出INF的经典原因如果你老老实实按模板写但运行结果不对最大的概率是存图时漏了无向边。这是我说的第一大坑我可以负责任地说至少三分之一的新手第一次提交热浪都死在这。排查思路先在addEdge里加一条cerr u - v w endl;跑一遍小样例看反向边到底有没有存进去。如果反向边没有那你的答案不等就怪了。另一个原因是起点和终点没读入对或者题目输入的s和t和你的变量名对不上检查一下输入顺序。再一个是把终点城市写成了起点自己这种情况如果起点就是终点输出应该是0要是你输出了INF肯定哪一行初始化出了问题。5.2 优先队列判重的两种方式的坑用vis数组的方式一定记得在更新邻居前检查if (!vis[v])。有些人偷懒不加这个判断因为就算加了正确性也不受影响——重复压入一个已经确定的点出堆时候会被vis拦截。但效率会有微小损失理论上每个点会被多余更新多次。用d ! dist[u]的方式有个极端情况如果两个不同方案算出的距离恰好相等比如dist[u]本来是3又有个路径也算出3那d ! dist[u]不成立这个节点就会被错误地当成“不是脏数据”而继续处理但它的邻居可能已经被更新过了。虽然正确性没有大碍但那种情况下会造成重复处理。所以更严谨的写法是再配合一个vis数组双保险。我自己用vis主要就是因为这个心理踏实。5.3 INF设置小了导致答案离奇有些题目边权很大累计距离可能超过10^9如果你INF设成1e9某条路径真实距离恰好超过1e9就会在更新时被误判成“距离没变小”从而丢了真正的答案。0x3f3f3f3f是4字节int下大概10.6亿许多题目边权之和可能比这个还大。这时可以把dist数组类型换成long longINF设成0x3f3f3f3f3f3f3f3f。热浪这道题倒没这么极端但我见过的许多省选题会卡这个点所以养成习惯——看到边权累计可能很大的题直接用long long队列配long long距离数组避免事后大规模改代码。5.4 SPFA在正权图上的隐患你可能在某篇博客里看到SPFA也能过热浪速度还不慢。但我的建议是正权图一律别用SPFA。SPFA在最坏情况下的复杂度是O(NM)而且存在精心构造的数据能把它卡到超时。即使热浪测试数据对SPFA友好你也不能保证考场那道改编题同样友好。Dijkstra堆优化的复杂度是严格O(MlogN)在正权图上永远正确不存在被卡的可能性。这就是我反复强调“见正权选堆优”的原因。如果你学的算法体系里面SPFA先入为主我建议在这道题上强制自己只用堆优化Dijkstra写三遍把习惯扭过来。6. 本题的扩展思考与后续进阶6.1 从热浪到P4779的差距热浪做完之后你的下一步训练题目很明确——洛谷P4779【模板】单源最短路径标准版。这题和热浪在算法核心上完全一致但数据范围放大到N10万、M20万边权最大1e9。如果你热浪的堆优化Dijkstra写得熟练P4779应该能在10分钟内默写完并一次通过。能过P4779你的正权最短路基础就算打牢了。再往后可以学带堆优化的Prim算法求最小生成树因为它的思想跟Dijkstra非常相似甚至可以复用同一套优先队列模板。你到时会发现图论算法之间很多逻辑是互相借用的前期把基础模板练得越熟练后期新算法学起来越顺。6.2 一条最短路径长什么样的验证技巧做题时如果你不确定答案对不对可以自己构造几个小样例来验证。比如3个城市1到2距离52到3距离71到3直连距离100那么最短时间应该是12走中转路而不是100。如果程序输出100说明松弛逻辑有问题不会从2中转。又比如两条完全一样的重边一条权值是10一条是8最终答案应该是8而不是10。用这种小样例验证代码非常高效比盲查代码快得多。我写任何最短路题都会先自己测一组三角形结构数据确保基础松弛逻辑没问题再提交评测。6.3 这类题在比赛中的分数占比热浪这种模板难度在最短路题里属于偏简单的但它对应的知识模块在省选、提高组里仍然频繁考察。很多难题是在Dijkstra基础上叠加拆点、分层图、状态压缩等维度核心架子还是这套。把热浪吃透等于给自己搭建了一个可以不断往上加功能的稳固地基。所以别因为是模板题就轻视考场里最快的选手往往不是会很多高级算法的人而是把基础算法写得滴水不漏的人。今天花两个小时把热浪的每个细节都吃透将来遇到任何最短路变种题你心里都有底。7. 我的实操体会与建议热浪这道题我在给学员讲的时候经常让他们做一个小挑战不看模板从零默写限时8分钟要求一次通过。第一次能做到的人非常少绝大部分都会在某个细节上卡一下要么忘了初始化head为-1要么忘了加无向边的第二条要么把优先队列的小根堆写成了大根堆。这其实是一件特别好的事因为考试的时候你根本没有调试器可用所有错误都只能靠肉眼发现。平时把这些错误全部提前犯一遍考场上就能一眼识别自己代码里的问题。我给自己的学生定了一个规矩凡是模板级别的题目必须练到“闭着眼也能写对”的程度。热浪就是最适合练这一关的题目之一。你今天把它写对了明天写P4779就会觉得无比轻松。最后再分享一个小技巧练习最短路时尽量准备一个自己最趁手的模板文件存好链式前向星、堆优化Dijkstra、初始化代码考试时遇到同类型题直接默写改编就好。模板越趁手你留出来思考难题的时间就越多。热浪值得你把它吸收进自己的模板库。 热浪P1379：堆优化Dijkstra最短路算法详解与模板实现
1. 题目拆解与算法选型1.1 题目到底在考什么“热浪(heatwv)”这道题在信息学奥赛一本通里是P1379如果我没记错的话位置在第八章图论算法的“最短路径”那一节紧跟在Dijkstra算法的例题组里是一道非常典型的正权图单源最短路入门题。题目本身的故事背景很直观德克萨斯州遭遇了一股热浪你所在的城市和另外一个城市之间有若干条公路连接每条公路的通行时间不同现在要求你从出发城市赶到目标城市的最短时间。把这个问题翻译成图论语言就是——给定一张N个点M条边的无向连通图边权为正求从起点s到终点t的最短路径长度。你可能觉得这道题看起来平平无奇但它被放在一本通里作为Dijkstra算法训练题是有讲究的。它考察的点其实非常清晰你会不会针对题目的数据范围选择合适的最短路算法你会不会写邻接表/链式前向星的存图方式你会不会用优先队列优化Dijkstra的常规模板你会不会处理无向边在存图时“加两条有向边”的细节你的初始化与松弛操作有没有写对。这些点和五年前考试的时候相比没什么变化今天依然是OI入门选手必须趟过去的一关。所以别急着刷下一题这道题值得你把每一行代码掰开揉碎弄明白。1.2 数据范围决定算法选择做题第一步永远不是写代码而是看数据范围。我记得一本通里这道题的N不超过2500M不超过6200边权都是正整数且规模不大。这个数据范围是比较友好的但它恰好位于“朴素Dijkstra能过但不太轻松”和“堆优化Dijkstra稳如泰山”的临界区域附近。用朴素Dijkstra也就是O(N^2)的写法在这个数据量下其实也能过因为2500的平方大概是六百多万次操作对于C在1秒时限内依然可以接受。但这里有个问题如果你习惯了朴素写法遇到N到达10万、20万的题就会立刻抓瞎。所以我的建议非常明确——直接学堆优化Dijkstra也就是O((NM)logN)的版本一步到位。这道题就是你练习堆优化写法最好的靶场。至于SPFA虽然也能过这道题但我不建议在正权图上使用。原因后面会在常见问题里细说这里先给个结论见正权图最短路默认堆优化Dijkstra不要给自己留用SPFA偷懒的毛病。1.3 为什么这道题值得反复写很多选手刷题喜欢追求数量但这道题我建议你至少独立写三遍。第一遍照着模板敲第二遍不看任何资料默写第三遍尝试加入不同的存图方式和手写堆。为什么这道题基本涵盖了图论最短路里最重要的基本功。存图方式选不好后面所有图论题都会束手束脚优先队列写不熟练很多贪心类题目也会受影响。热浪的代码量大概在六七十行不长不短恰好适合反复锤炼。我记得当年学这道题的时候第一次用邻接矩阵写了一遍然后又用vector邻接表写了一遍最后才上手链式前向星。三种存图方式各跑一遍之后对Dijkstra的理解才算真正扎实了。你可以在后面参考我给的实现但更希望你自己独立写完一遍再回来看效果完全不同。2. Dijkstra算法核心原理解读2.1 贪心思想的直观理解Dijkstra算法的本质是贪心不理解贪心就记不住模板。我用一个特别生活化的方式给你讲明白。想象你在学校操场中央要去操场另一头的商店买东西操场上有很多岔路你不知道哪条路最近。你手上有一个记录本和一个标记笔记录本上写着每个路口距离你当前出发点的最短估计距离一开始只有起点是0其他都是无穷大。算法做的事其实非常“笨”每次在所有还没确定最短距离的路口中挑一个当前记录距离最小的认为这个路口的最终最短距离已经确定了然后用这个路口去更新它旁边所有路口的记录距离如果经过这个路口能更近的话。重复这个过程直到所有路口都被标记。关键就在于“每次挑当前距离最小的出来”这个动作这就是贪心。为什么敢这么挑因为你已经选出来的点它的距离是通过一些比它更近的点更新过的而这些更近的点都已经确定最终距离了所以这个“最小距离”不可能再被其他路径更新得更小。严格证明依赖边权非负——如果边权是负数后面可能出现一条负边把曾经确定的距离改小贪心就失效了。用这个操场的比喻你再回看代码每一行都能对上号。2.2 各步骤的时间复杂度为什么这样朴素Dijkstra找最小点的过程是每次都扫描一遍所有未标记节点复杂度是O(N^2)。N很小没事N一大就成了瓶颈。堆优化Dijkstra的核心就是用一个优先队列小根堆来维护“当前距离最小的未确定点”让找最小点的动作从O(N)变成O(logN)。每条边最多被松弛一次所以总复杂度是O(MlogN)空间上多维护一个堆是O(N)。这道题M小于N的三倍左右用堆优化的优势还不太明显但你已经能感受到“每条边只会被拿出来更新一次”的简洁逻辑。等以后遇到M很大、N也大的图这个优势会放大得非常明显。2.3 边权非负为什么如此关键我刚才反复强调边权非负是因为Dijkstra的整个正确性建立在“已经确定距离的点不可能再被其他未确定的点更新得更短”这个前提上。而负权边专治这种自信。举个例子假设一条边权是-100的边连接起点和一个远方的点只通过这条负边远方点的距离立刻变成-90而它的“估算距离”比起点到其他邻居都小得多。如果算法此时把这个远方点当作确定点后面就算有别的路径把它更新得更小也已经来不及了。这个点一错后面全是错的。所以在看这道题的时候你一定留意到题目并没有负边所有道路的通行时间都是正整数。这就是命题人在告诉你——放心大胆用Dijkstra我故意没给你设负权坑。但也正因为很多题都靠这个特点送分你更要养成看题目条件的好习惯考试时先检查边权正负再决定算法。3. 完整代码与核心细节实现3.1 链式前向星存图写法先给出我推荐的完整代码使用的是链式前向星存图。这是OI竞赛里综合效率最稳妥的存图方式内存紧凑遍历速度快写熟了之后很多图论题都能通用。#include bits/stdc.h using namespace std; const int MAXN 2500 5; const int MAXM 6200 * 2 5; const int INF 0x3f3f3f3f; struct Edge { int to, w, next; } edge[MAXM]; int head[MAXN], tot; int dist[MAXN]; bool vis[MAXN]; void addEdge(int u, int v, int w) { edge[tot].to v; edge[tot].w w; edge[tot].next head[u]; head[u] tot; } struct Node { int id, d; bool operator(const Node other) const { return d other.d; // 小根堆 } }; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] 0; priority_queueNode pq; pq.push({s, 0}); while (!pq.empty()) { Node cur pq.top(); pq.pop(); int u cur.id; if (vis[u]) continue; vis[u] true; for (int i head[u]; i ! -1; i edge[i].next) { int v edge[i].to; int w edge[i].w; if (!vis[v] dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({v, dist[v]}); } } } } int main() { int n, m, s, t; memset(head, -1, sizeof(head)); cin n m s t; for (int i 0; i m; i) { int u, v, w; cin u v w; addEdge(u, v, w); addEdge(v, u, w); } dijkstra(s); cout dist[t] endl; return 0; }这个模板是我改了很多版之后稳定使用的版本有几个细节你考试时也照这样写基本不会翻车。edge数组大小开成MAXM * 2是因为无向边要存两遍宁多勿少。INF用0x3f3f3f3f是一个技巧它的十进制是1061109567足够大而且memset可以直接按字节初始化成这个值不用循环赋值。priority_queue默认是大根堆所以要重载让比较逻辑反过来或者用greaterNode哪种顺眼用哪种。最核心的if (vis[u]) continue是因为同一个点可能被多次压入堆中不跳过会白做很多无效松弛。3.2 为什么每次出堆都要判重堆优化Dijkstra有一个非常经典的细节——一个点可能被加入优先队列很多次但真正被确定最短距离、用来更新邻居的次数只有一次。为什么每次松弛操作发现距离能变小就把新的状态压入堆中所以同一个点可能以不同距离出现好几次。堆中距离最小的那次出堆就是这个点的最终最短距离。此后如果又轮到同一个点出堆但此时它的距离一定比之前那次大说明它已经被确定过了直接跳过即可。这个判重操作就是vis数组存在的原因。如果不判每个点每次出堆都会去扫描它所有的邻居复杂度会退化成接近O(MN)后果不堪设想。所以vis不是可有可无的装饰是性能的保命符。另一种常见写法是不用vis出堆时判断cur.d ! dist[u]不等就跳过。两种写法等价选一种自己习惯的、不容易记混的就好。我习惯用vis数组因为语义清楚调试时一看就知道哪些点确定了。3.3 初始化边长数组的隐患存图之前要把head数组全部初始化为-1这个操作很多新手会忘记。如果用邻接表存图这个细节直接决定你的遍历对不对。我见过有人用是0来初始化head然后addEdge里面edge[i].next head[u]这样第一个边指向0循环边界就出问题。所以建议直接约定head数组初始化为-1遍历时用i ! -1做终止条件。还有一个隐患是如果你的题目给了重边——同一对城市之间有多条道路时间不同你的addEdge天然支持存储多条边但如果你用的是邻接矩阵存图就必须在输入时取最小值。热浪这道题我没记错的话不卡重边但养成处理重边的习惯是好的后面很多图论题都会遇到。3.4 无向图存边的正确姿势题目明确说公路是双向的也就是说你可以从A城市到B城市也能从B城市到A城市。所以在addEdge时一定要调两次函数把两条相反方向的边都存进去。很多选手第一次写这道题栽在这里只加了一条方向的边结果输出永远是INF怎么调都不对。半天的调试时间就这么浪费了。我建议在main函数里加边部分固定写成一个注释标记的头每次看到就提醒自己“这是无向图要调两次”。如果你的addEdge函数写的是按引用改head和tot那加边的顺序没有影响。唯一要求是两条边都要加。4. 两种模板写法对比与选型建议4.1 vector邻接表的实现除了链式前向星vector邻接表可能是平时刷题更常见的写法因为写起来更直观。我也给你一个可以直接用的版本#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 2500 5; struct Node { int v, w; }; vectorNode g[MAXN]; int dist[MAXN]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto cur pq.top(); pq.pop(); int d cur.first, u cur.second; if (d ! dist[u]) continue; for (auto e : g[u]) { int v e.v, w e.w; if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } } 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(s); cout dist[t] endl; return 0; }这里用的是priority_queuepairint,int, vectorpairint,int, greaterpairint,intpair排序时先比first也就是距离再比second也就是节点编号逻辑完全符合需求。判重用了d ! dist[u]效果和vis一样。vector写法在热浪这种小数据上完全够用代码也更易读适合平时练习和写模板题。缺点是动态开辟内存需要频繁push性能略低于静态数组的链式前向星但数据量小时差距微乎其微。4.2 链式前向星的优势与适用场景我最终更推荐链式前向星原因有三点第一静态数组分配好内存之后不再动态申请在极端大数据的图论题里更稳第二遍历边时通过next指针跳转cache局部性更好一些实测在百万级边的时候有优势第三很多进阶图论算法如网络流、费用流也要用链式前向星存残余网络提前练熟等于一步到位。但链式前向星对新手确实不太友好看起来就是一个链表的数组实现调试时看不清楚。所以我不建议新手一上来就用它——先用vector把算法逻辑打通再回头用链式前向星优化。两个版本都跑一遍热浪你再感受一下哪个细节容易出错这比直接背一个模板更有价值。4.3 邻接矩阵为什么不该用回到热浪这道题N最大2500如果开邻接矩阵就需要2500×2500个int大概25MB内存其实还是能扛得住的。所以我见过不少初学者用邻接矩阵写这道题也过了但我不建议你这么做。邻接矩阵最大的问题是它只能存一条边遇到重边必须手动取最小值同时遍历时O(N^2)扫描无法跳过不存在的边。如果这道题的N改成10万邻接矩阵直接内存爆炸。你需要养成一个习惯看到图论题先看N范围再决定存图方式。一般来说N大于5000就该毫不犹豫放弃邻接矩阵。5. 常见问题排查与避坑心得5.1 输出INF的经典原因如果你老老实实按模板写但运行结果不对最大的概率是存图时漏了无向边。这是我说的第一大坑我可以负责任地说至少三分之一的新手第一次提交热浪都死在这。排查思路先在addEdge里加一条cerr u - v w endl;跑一遍小样例看反向边到底有没有存进去。如果反向边没有那你的答案不等就怪了。另一个原因是起点和终点没读入对或者题目输入的s和t和你的变量名对不上检查一下输入顺序。再一个是把终点城市写成了起点自己这种情况如果起点就是终点输出应该是0要是你输出了INF肯定哪一行初始化出了问题。5.2 优先队列判重的两种方式的坑用vis数组的方式一定记得在更新邻居前检查if (!vis[v])。有些人偷懒不加这个判断因为就算加了正确性也不受影响——重复压入一个已经确定的点出堆时候会被vis拦截。但效率会有微小损失理论上每个点会被多余更新多次。用d ! dist[u]的方式有个极端情况如果两个不同方案算出的距离恰好相等比如dist[u]本来是3又有个路径也算出3那d ! dist[u]不成立这个节点就会被错误地当成“不是脏数据”而继续处理但它的邻居可能已经被更新过了。虽然正确性没有大碍但那种情况下会造成重复处理。所以更严谨的写法是再配合一个vis数组双保险。我自己用vis主要就是因为这个心理踏实。5.3 INF设置小了导致答案离奇有些题目边权很大累计距离可能超过10^9如果你INF设成1e9某条路径真实距离恰好超过1e9就会在更新时被误判成“距离没变小”从而丢了真正的答案。0x3f3f3f3f是4字节int下大概10.6亿许多题目边权之和可能比这个还大。这时可以把dist数组类型换成long longINF设成0x3f3f3f3f3f3f3f3f。热浪这道题倒没这么极端但我见过的许多省选题会卡这个点所以养成习惯——看到边权累计可能很大的题直接用long long队列配long long距离数组避免事后大规模改代码。5.4 SPFA在正权图上的隐患你可能在某篇博客里看到SPFA也能过热浪速度还不慢。但我的建议是正权图一律别用SPFA。SPFA在最坏情况下的复杂度是O(NM)而且存在精心构造的数据能把它卡到超时。即使热浪测试数据对SPFA友好你也不能保证考场那道改编题同样友好。Dijkstra堆优化的复杂度是严格O(MlogN)在正权图上永远正确不存在被卡的可能性。这就是我反复强调“见正权选堆优”的原因。如果你学的算法体系里面SPFA先入为主我建议在这道题上强制自己只用堆优化Dijkstra写三遍把习惯扭过来。6. 本题的扩展思考与后续进阶6.1 从热浪到P4779的差距热浪做完之后你的下一步训练题目很明确——洛谷P4779【模板】单源最短路径标准版。这题和热浪在算法核心上完全一致但数据范围放大到N10万、M20万边权最大1e9。如果你热浪的堆优化Dijkstra写得熟练P4779应该能在10分钟内默写完并一次通过。能过P4779你的正权最短路基础就算打牢了。再往后可以学带堆优化的Prim算法求最小生成树因为它的思想跟Dijkstra非常相似甚至可以复用同一套优先队列模板。你到时会发现图论算法之间很多逻辑是互相借用的前期把基础模板练得越熟练后期新算法学起来越顺。6.2 一条最短路径长什么样的验证技巧做题时如果你不确定答案对不对可以自己构造几个小样例来验证。比如3个城市1到2距离52到3距离71到3直连距离100那么最短时间应该是12走中转路而不是100。如果程序输出100说明松弛逻辑有问题不会从2中转。又比如两条完全一样的重边一条权值是10一条是8最终答案应该是8而不是10。用这种小样例验证代码非常高效比盲查代码快得多。我写任何最短路题都会先自己测一组三角形结构数据确保基础松弛逻辑没问题再提交评测。6.3 这类题在比赛中的分数占比热浪这种模板难度在最短路题里属于偏简单的但它对应的知识模块在省选、提高组里仍然频繁考察。很多难题是在Dijkstra基础上叠加拆点、分层图、状态压缩等维度核心架子还是这套。把热浪吃透等于给自己搭建了一个可以不断往上加功能的稳固地基。所以别因为是模板题就轻视考场里最快的选手往往不是会很多高级算法的人而是把基础算法写得滴水不漏的人。今天花两个小时把热浪的每个细节都吃透将来遇到任何最短路变种题你心里都有底。7. 我的实操体会与建议热浪这道题我在给学员讲的时候经常让他们做一个小挑战不看模板从零默写限时8分钟要求一次通过。第一次能做到的人非常少绝大部分都会在某个细节上卡一下要么忘了初始化head为-1要么忘了加无向边的第二条要么把优先队列的小根堆写成了大根堆。这其实是一件特别好的事因为考试的时候你根本没有调试器可用所有错误都只能靠肉眼发现。平时把这些错误全部提前犯一遍考场上就能一眼识别自己代码里的问题。我给自己的学生定了一个规矩凡是模板级别的题目必须练到“闭着眼也能写对”的程度。热浪就是最适合练这一关的题目之一。你今天把它写对了明天写P4779就会觉得无比轻松。最后再分享一个小技巧练习最短路时尽量准备一个自己最趁手的模板文件存好链式前向星、堆优化Dijkstra、初始化代码考试时遇到同类型题直接默写改编就好。模板越趁手你留出来思考难题的时间就越多。热浪值得你把它吸收进自己的模板库。