“小苯的最短路”光看这个名字你可能以为是个小朋友写的童话故事但只要你是在算法圈里混过的一眼就能认出来——这是很多高校新生赛、算法入门课里常见的一类题目。用“小苯”当主角无非是让题目显得没那么冷冰冰但题面背后考的东西一点都不会手软最短路径图论里最经典也最实用的模型之一。这篇文章我就借着“小苯的最短路”这个题名把最短路这一整块内容好好捋一遍。从最基础的Dijkstra堆优化到很多新手一听就懵的“分层图最短路”再到做题时真正会踩的坑、常用的调试技巧一次性讲清楚。无论你是刚学图论的大一新生还是在备战ACM、蓝桥杯、考研机试的老手这篇内容都值得你花十分钟认真看完。1. 小苯这道题到底在考什么1.1 最短路不是一种算法而是一类模型很多新手一开始会犯一个认知上的错误就是觉得“最短路 Dijkstra”。实际上最短路是一类问题的总称它下面按照图的性质不同分出了好几套算法体系单源正权图最短路最典型的就是Dijkstra配合堆优化之后能做到O((nm)log n)的复杂度是竞赛里的绝对主力。单源负权图最短路Bellman-Ford以及它的队列优化版SPFA。虽然SPFA在随机图上跑得飞快但遇上构造数据会被卡到O(nm)所以现在很多比赛都刻意卡SPFA。多源多汇最短路Floyd-WarshallO(n^3)的复杂度注定了它只能用在定点数很少的场景一般n 500。特殊图最短路比如边权只有0和1的图可以用01BFS边权都是正数且可以用A*加速的还有拓扑图上的DP也能解决一类最短路问题。“小苯的最短路”这种题之所以在新生赛里高频出现就是因为它把“读题 - 抽象成图 - 选择算法 - 实现 - AC”这一整套流程串起来了。它不会在算法的难度上卡你但会在你对图论模型的敏感度上卡你。1.2 从数据范围判断该用什么算法我反复跟学弟学妹强调一句话拿到图论题先看数据范围再看题目意思。数据范围直接决定了你要用哪套算法很多时候你把范围看明白了解法就浮出水面了。假设小苯的题目里n点数和m边数都给到了10^5这个量级那Floyd想都不用想O(n^3)直接爆炸。SPFA在出题人随便出一组网格图的情况下也能被卡到TLE剩下最稳妥的就是堆优化的Dijkstra。但如果你仔细读题发现边权有可能为负那Dijkstra也不能用得换思路。所以做题的第一步永远是把数据范围抄在草稿纸上把边权性质圈出来再决定算法方向。1.3 为什么我说这题是“入门图论的第一块跳板”小苯这类题好在哪呢好在它把图论里最核心的几个概念全部带出来了建图、邻接表、优先队列、松弛操作、复杂度分析。你把这题吃透了后面再学网络流、最小生成树、二分图匹配很多底层的东西都是相通的。我在带新生训练的时候有个很直观的感受能把“小苯的最短路”这种题讲明白的同学后面学图论普遍不会太吃力反而是一上来就啃“缩点Tarjan”的大概率是看了一堆博客但代码一行都没敲。图论这东西真的不能只看必须上手写。2. 核心算法实现与细节拆解2.1 堆优化Dijkstra的完整实现最短路的核心思想我用大白话给你说清楚假设你现在站在起点手里有一张地图。你每次走到一个路口都看看从当前路口能不能绕到邻居那边让邻居到起点的距离变得更短。如果能就更新邻居的距离。这个过程叫“松弛”。Dijkstra和普通BFS最大的区别在于BFS是按层扩展而Dijkstra是每次从“当前已知距离最小但还没确定的点”出发去扩展。所以需要一种数据结构来快速取最小值这就是优先队列的用武之地。#include bits/stdc.h using namespace std; const int MAXN 1e5 5; const long long INF 1e18; struct Edge { int to; int w; }; vectorEdge graph[MAXN]; long long dist[MAXN]; bool visited[MAXN]; void dijkstra(int start) { // 初始化距离为无穷大 fill(dist, dist MAXN, INF); memset(visited, 0, sizeof(visited)); // 小顶堆pair的第一个元素是距离第二个是节点编号 priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; dist[start] 0; pq.push({0, start}); while (!pq.empty()) { auto [curDist, u] pq.top(); pq.pop(); // 如果这个点已经处理过跳过 if (visited[u]) continue; visited[u] true; // 尝试松弛所有邻居 for (const Edge e : graph[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}); } } } }这段代码有一个很关键的细节if (visited[u]) continue;。因为优先队列里同一个点可能被推入多次每次距离被更新就会推一次弹出时如果已经是处理过的状态就直接忽略这个判断能保证每个点只会被真正扩展一次时间复杂度才能稳定在O((nm)log n)。2.2 优先队列里到底该放什么很多新手写Dijkstra堆优化最容易纠结的就是优先队列里的类型。我的建议是直接用pairlong long, intfirst放距离second放节点编号。为什么距离要放前面因为pair默认按first排序而我们需要的就是按距离出队。但如果你追求极致性能可以自定义结构体重载运算符struct Node { long long dist; int id; bool operator(const Node other) const { return dist other.dist; // 注意这里要反过来让优先队列变成小顶堆 } };用greaterpairlong long, int还是自定义结构体其实差别不大比赛里我用pair居多因为代码短、不容易写错。不过要提醒你一点dist必须用long long。如果题目说边权最大是10^9n是10^5那么路径距离最坏能达到10^14int直接溢出这是最短路题最容易翻车的地方。2.3 建图方式vector邻接表还是链式前向星既然提到建图就多说两句。C选手最常用的建图方式有两种vector嵌套vectorEdge graph[MAXN]。代码直观遍历方便适合大多数题目。链式前向星用数组模拟链表head[]、to[]、nxt[]、w[]。代码稍微复杂但静态数组访问的缓存友好性更好在某些极限数据下会更快。我在新生赛阶段建议你无脑用vector邻接表因为代码可读性强不容易写错。等你用顺手了、需要极限优化的时候再切链式前向星也不迟。图论题最重要的不是节省那几十毫秒而是保证一次写对。2.4 手推一遍Dijkstra把“松弛”焊死在脑子里光看代码不手推过两天就忘了。我教你一个笨办法拿一组小数据把dist数组的变化过程在纸上画出来。假设有4个点边是这样的1-2权重21-3权重52-3权重13-4权重1。起点是1。初始状态dist[1]0dist[2]infdist[3]infdist[4]inf。取出距离最小的点1松弛邻居2和3dist[2]2dist[3]5。取出距离最小的点2距离2松弛邻居3dist[2]13 dist[3]5所以dist[3]更新为3。取出距离最小的点3距离3松弛邻居4dist[4]4。取出距离最小的点4没有邻居结束。你看到没有关键就是这步2到3这条边让原本走1-3的5变成了1-2-3的3。这就是“松弛”的直观意义——通过中间点绕路反而更近了。3. 从“小苯”到分层图最短路让题目再难一点3.1 什么是分层图为什么要分层如果你觉得“小苯的最短路”只是考个裸Dijkstra那你就低估出题人的心思了。很多学校的选拔赛会在“小苯”系列题里埋一个进阶点——分层图最短路。这玩意儿在竞赛里太常用了特别是那些“可以K次免费/打折/绕路”的题目本质上都在考分层图。先理解一个场景小苯要从家到学校图上有n个路口和m条道路每条路有一个通行时间。现在小苯手里有k张“免单券”也就是最多可以选k条边把它的权值变成0。问从家到学校最少需要多少时间如果你按普通的最短路来想坏就坏在“k”上——到底免哪几条边收益最大这个决策不能提前知道得边跑边选。直接暴力枚举哪些边用券那就是O(C(m,k))妥妥爆炸。分层图就是专门解决这类问题的。3.2 分层图最短路的核心原理所谓分层图就是把原来的图复制成k1层每一层都代表“已经用了0次券、用了1次券……用了k次券”的状态。连接方式是这样的如果在原图中有一条u到v、权值为w的边那么在第i层i从0到k-1我们额外加一条从第i层的u到第i1层的v、权值为0的边。这条权值为0的边就代表“用了1次券、从第i层穿越到第i1层”。形象点说你每一层都有一份完整的城市地图层与层之间的“免费通道”是单向的只能从低层往高层走不能回头。这样从“第0层的起点”跑到“第k层的终点”的最短距离就是答案。解释一下为什么最后要跑到第k层因为题目允许最多用k次券你可能会用掉0次、1次、2次……最多k次。所以在终点那一列我们要看的是第0层到第k层所有“终点”的最小值。当然如果你把所有层的终点都连一条权值为0的边到同一个汇点那你直接跑一次Dijkstra、看汇点的dist就行了。3.3 分层图的最短代码模板分层图最短路写起来并不复杂最直接的办法就是把节点编号扩展一维原本的节点编号是u扩展后就是u layer * n。建图的时候每一层内部的边照建层与层之间再加“免费边”。#include bits/stdc.h using namespace std; const int MAXN 1e5 5; const int MAXK 15; const long long INF 1e18; struct Edge { int to; int w; }; vectorEdge graph[MAXN * (MAXK 1)]; long long dist[MAXN * (MAXK 1)]; bool visited[MAXN * (MAXK 1)]; void add_edge(int u, int v, int w) { graph[u].push_back({v, w}); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k, s, t; cin n m k s t; // s是起点t是终点 for (int i 0; i m; i) { int u, v, w; cin u v w; // 在第0层到第k层都建原边 for (int layer 0; layer k; layer) { add_edge(u layer * n, v layer * n, w); add_edge(v layer * n, u layer * n, w); } // 层与层之间建立免费边单向 for (int layer 0; layer k; layer) { add_edge(u layer * n, v (layer 1) * n, 0); add_edge(v layer * n, u (layer 1) * n, 0); } } // 跑从起点(s)到所有点的Dijkstra // 最后答案是 min(dist[t layer * n]) for layer in 0..k // 或者把t的各层终点连到一个超级终点直接输出超级终点的dist // 为了稳妥可以建一个超级终点T n * (k 1) int superT n * (k 1); for (int layer 0; layer k; layer) { add_edge(t layer * n, superT, 0); } // 对 superT 跑 Dijkstra 是不对的应该从起点s跑 // 记住从起点出发 // dijkstra(s); // cout dist[superT] endl; return 0; }上面的代码思路是对的但有两点新手特别容易搞混第一超极终点要连的是“入边”还是“出边”我们要从起点往终点跑所以最后是把每一层的终点连一条权值为0的边指向超级终点然后从起点开始跑Dijkstra最后dist[superT]就是答案。第二免费边的方向千万别搞反。只能从低层指向高层一旦你写成从高层指向低层就会出现“先免了再还回去”的循环答案就错了。3.4 分层图模型能解决的三类经典变式分层图最短路不只是用来做“免费券”的我把常见的变式给你总结一下方便你举一反三最多k条边权变为0这就是上面讲的免费券模型。最多k条边权减半把权值为0的边改成权值为w/2就行但要注意整数除法还是浮点数题目会给清楚。必须恰好经过k个特殊点这个不能只靠分层图通常要结合状态压缩旅行商问题或拆点技巧。另外分层图的思想还能用在“时间维度”上。有些题目里你不仅要考虑空间的移动还要考虑时间的变化比如公共交通的班次、红绿灯的等待这时候把“时间”当成一层维度也能用类似建图的方式解决。这就是为什么我一直强调分层图的本质是“在原有的图上增加状态维度”只要你能把决策状态想清楚很多看似复杂的题都能转化为最短路问题。4. 常见错误与调试技巧实录4.1 初始化与访问顺序的致命细节最短路题80%的错都出在初始化上。你想想dist数组没有初始化成INF初始值是0那Dijkstra跑出来的结果全乱了visited数组没清空第二次跑Dijkstra的时候直接跳过所有点。这些错误都很低级但越是高压的比赛环境里越容易犯。我的习惯是写一个init()函数统一做三件事void init(int n) { for (int i 0; i n; i) { graph[i].clear(); dist[i] INF; visited[i] false; } }每次跑新的测试数据之前调用一次干净利落。很多队伍的模板里都有这个函数我强烈建议你也养成这个习惯。4.2 优先队列里距离相等的点顺序会影响结果吗先说结论不影响最终最短路的正确性但可能会影响你调试时看到的执行过程。因为优先队列只保证“最小的先出来”对于dist相同的一堆节点它们的弹出顺序是不确定的。这很让人头疼因为你看同一个数据两次运行的过程可能不一样但结果应该一样。如果结果不一样那说明你的松弛逻辑有问题跟优先队列本身无关。这里给你一个调试诀窍在代码里临时加一个printf每次从优先队列里弹出节点u的时候打印当前的u和dist[u]。如果发现某个节点被弹出时dist[u]不等于它入队时记录的距离说明你的优先队列里存的是旧值但你的visited判断又把它拦住了这种情况属于正常现象。真正的问题往往出在“错误地更新了visited”或者“没更新dist就push”上。4.3 用对拍器验证你的程序我经常跟来问问题的同学说别问我为什么不对先学会对拍。对拍的基本流程是这样的写一个暴力程序比如Floyd或者BFS能算正确答案就行不用管复杂度。写一个数据生成器随机生成小规模图比如n5到10边权随机1到10。写一个bat脚本或shell脚本循环生成数据分别跑暴力程序和你的优化程序比对输出。只要有一次输出不一致恭喜你你找到了一个反例。接下来就拿着这组数据去调试看是哪里处理出错了。对拍器的价值怎么强调都不为过它能把“玄学错题”变成“确定性bug”。下面给一个简单的对拍脚本示例Windows环境echo off :loop gen.exe data.in brute.exe data.in brute.out solution.exe data.in solution.out fc /brute.out solution.out nul if errorlevel 1 ( echo Wrong Answer on data.in pause goto :end ) echo Test passed goto :loop :endLinux环境用Shell脚本也一样核心思路就是循环比对。4.4 内存估算别让小数组毁了你的AC分层图最短路最大的坑其实是数组开小。你想想原来是n个点分了k层之后节点数变成n*(k1)边数也要乘以(k1)。如果你只按原来的MAXN开数组那可不得越界吗越界的情况下程序不一定立刻崩溃而是可能悄悄覆盖了其他变量的内存导致各种诡异现象——所以每次写分层图我都会在代码开头先算一下最大节点数再决定数组大小。举个例子n100000k5那么总节点数就是600001。再加上超级终点你至少要开600005以上的数组。边数方面m200000有向边每层都要建再加上层间免费边数量在m*k级别用vector存就不用太担心但用链式前向星就得提前算好总边数。5. 从“小苯”出发通向更远的图论世界5.1 最短路之外还有哪些图论模型值得学把“小苯的最短路”调通了你其实已经把图论里最重要的一条技能树点亮了一半。接下来可以顺着这条线继续深入最小生成树和最短路的区别是它找的是连接所有点的最小总权值的边集算法用Kruskal或Prim。逻辑上比最短路简单但并查集要熟练掌握。拓扑排序与关键路径给有向无环图DAG做线性排序是很多动态规划题的前提。强连通分量Tarjan缩点把有向图中的环缩成一个点把一般图变成DAG就能用DP处理。这是图论里的高级操作应用极广。网络流最大流最短路是“一个点到另一个点的最短路径”最大流是“从源点到汇点最多能运多少流量”思想上有相通之处但实现起来又是一个新世界。我的个人看法是最短路是图论的“指尖感觉”。你把Dijkstra练到肌肉记忆后面学网络流里的最短路增广、费用流都会觉得很顺。反过来如果你连Dijkstra都要现推模板那后面这些高级算法基本就是空中楼阁。5.2 一个强烈建议建立自己的模板库在竞赛圈摸爬滚打这么久我最想告诉你的一个建议是一定要建立并维护一份自己的代码模板库。所谓自己的模板库不是把别人的模板直接复制粘贴而是你亲手写过、反复踩过坑、加了注释、知道自己每一个变量含义的代码。比如Dijkstra模板、分层图模板、SPFA模板、Floyd模板每种都存一份。每次出题时直接调用自己的模板速度会快很多而且因为是你自己写的出错的概率也低得多。模板不是越复杂越好。我第一次参加区域赛的时候担心自己的模板太低端特意去找了网上“高端”的链式前向星手写堆版本。结果比赛时手写堆写挂了反而浪费了半小时。后来就老实了回归到自己最熟悉的vector优先队列模板稳得很。在比赛里你最有把握的代码才是好代码。6. 做题的节奏与训练心得说了这么多技术和代码最后聊点软性的东西——怎么刷图论题才有效率。我见过太多同学天天刷水题刷到100道还是只会模板题也有同学直接啃难题每道题看题解才能写写完转头就忘。这两种都不是健康的学习方式。我的建议是难度分层交替训练。第一层确保模板题滚瓜烂熟。就是“小苯的最短路”这种裸裸的Dijkstra你拿到题不用动脑手速飞快地写完。这一层练的是基本功和代码熟练度。第二层刷变式题。比如在题面上加了“有k次免费机会”这就要用到分层图比如无向图变成了带时间窗的图这就要想怎么拆点。这一层练的是模型迁移能力练的多了你会发现出题人再怎么包装核心还是那几板斧。第三层刷综合题。最短路和DP结合、最短路和二分答案结合、最短路和拓扑排序结合。这种题能考验你的全局观也是真正拉开差距的地方。我自己的习惯是每周固定抽两个晚上专门刷图论题每次3到4道不贪多但每道题做完之后会写一小段题解思路记录这题的关键点是什么、有没有一题多解、用到的技术能不能抽象成模板。坚持几个月之后图论模型的敏感度会有质的提升。最后再分享一个我调题时的独家小技巧如果你发现Dijkstra跑出来的dist数组里有某个点的距离还是INF而理论上它应该是可达的那一定不是算法的问题而是建图的问题。要么是边没加进去要么是节点编号写错了要么是数组没开够。这时候别盯着代码发呆回到建图的部分一条边一条边地打印出来对照问题很快就浮出水面了。“小苯的最短路”这个名字听起来轻松但它背后覆盖的知识密度足够一个初学者打磨一两个星期。从最基础的Dijkstra到可以解决“免费券”问题的分层图最短路再到建立起自己的模板库和刷题节奏这条路走通了你在图论这一块就算是真正入了门。接下来要做的就是多敲代码、多踩坑、多总结然后把每一次WA都当成通往AC的必经之路。