如果你刷过一段时间USACO大概率绕不开洛谷P2865这道Roadblocks G。它是图论里非常经典的“次短路”模板题洛谷题解区常年有讨论很多刚学完Dijkstra的选手都会在这里卡一下。题目本身不复杂但“最短路”和“次短路”要同时放进一个优先队列里维护第一次接触的人十有八九会栽在更新顺序上。这篇文章我想从题意、算法原理、AC代码、调试技巧到后续扩展完整地把这道题讲透适合已经会写普通Dijkstra、想再进一步搞懂次短路原理的读者。1. 看懂题目次短路到底是什么1.1 题意与样例推演先看原题。Roadblocks G 给定一张无向连通图点数为n边数为r每条边有正的边权。要求从1号节点走到n号节点找一条长度严格大于最短路的路径并且是所有这种路径里最短的一条输出它的长度。注意几个关键词无向图边权为正路径允许经过重复节点和重复边要找的是“严格大于最短路”的路径而不是“第二短”的路径如果最短路长度是L要输出的是所有长度大于L的路径中的最小值。原题样例是一个很好的理解入口。4个点、4条边数据长这样1-21002-42002-32503-4100这里从1到4的最短路显然是1-2-4长度300。但次短路是多少答案是450对应路径1-2-3-4长度为100250100450。注意不能选路径1-2-4再绕回2如果走1-2-4-3-4长度100200100100500也大于300但它不是最优次短路。所以这道题最后输出的结果是450。这个样例说明一个关键现象次短路往往和最短路共享一段前缀然后在某个路口分叉绕一段路再汇合回终点。这个观察对后面理解算法非常有帮助。1.2 严格次短与第二短路径的区别很多初学者把“次短路”理解成“除了最短路以外最短的路径”但题目里的“严格大于最短路”其实更严格。有一个容易被忽略的情况如果存在两条长度相同但路径不同的最短路比如1-2-4和1-3-4长度都是300那么“第二短的路径”可以是300但“严格次短路”不能是300必须比300大。在双状态Dijkstra的模板里这个严格性体现在一个很小的判断只有新路径长度严格大于当前最短路时才有资格去竞争次短路。收录长度相等的路径会把“严格次短”错算成“非严格次短”。USACO原题要求的是严格次短路所以这一点必须注意。从题目描述还能看出一个细节因为路径允许重复走所以只要图连通次短路一定存在。最极端的情况从1到n只有一条边最短路长为w次短路可以走1-n-1-n长度3w总归有解。这也是我们跑算法时不用额外判“无解”输出什么的原因。2. 算法选型为什么删边法不靠谱2.1 删边法的直觉与翻车点新手看到次短路最自然的想法是先跑一遍Dijkstra求出最短路然后枚举最短路上的每条边把这条边删掉再跑一次最短路取这些结果里最小的那个。这个思路听起来顺理成章但实际有两个硬伤。第一个硬伤是复杂度。最短路最多包含n-1条边每删一条边都要重新跑一遍Dijkstra总复杂度是O(n·(mn)logn)。n是5000时看起来还能忍但边数m如果是100000那就直接爆炸。而且这是最短路路径上的每一条边都要试不是一两次就能解决的。第二个硬伤更致命删边法本身在逻辑上就是错的。次短路不一定要通过“禁用最短路上的某条边”来获得。举个反例假设最短路是1-2-3-4其中2-3这条边特别短。另有一条备用路径1-2-5-4在2处分叉距离只比最短路长一点点。它的最优次短路完全可以直接走1-2-5-4并没有经过3也没必要“绕开2-3”。但如果用删边法比如删掉3-4那1-2-3-4这条最短路被破坏后重新求最短路可能得到1-2-5-4这恰好是次短。换个图结构比如备用路径先经过3再绕出去1-2-3-5-4这时删掉2-3或3-4都会让这条路径失效但完整的最优次短路恰恰依赖这两条边都存在。换句话说删边法枚举的候选集合和真实次短路径没有必然的对应关系正确性从一开始就无法保证。2.2 两种可AC解法的对比与选择抛开删边法这道题主流有两种正确解法。第一种是“最短路反向最短路枚举边”。先跑一遍从1出发的Dijkstra得到dis1再跑一遍从n出发的Dijkstra得到dis2无向图不需要建反图然后枚举原图中的每条边(u,v)和边权w用dis1[u]wdis2[v]以及dis1[v]wdis2[u]来更新答案最后取大于dis1[n]的最小值。这种解法的正确性基于一个重要观察任意一条路径如果在某个节点第一次偏离最短路那么这段路径可以拆成“从1到分叉点的最短路 一条偏离边 从偏离点到n的最短路”。因为从偏离点之后改用最短路得到的路径长度只会更短只要这个结果和原最短路不同它就是严格大于最短路的候选路径。所以枚举所有边覆盖了所有可能的分叉情况。第二种是“双状态Dijkstra”也就是同一个优先队列里同时维护每个点的最短路和次短路直到终点。这也是题解区最常见的写法代码短一次Dijkstra搞定思想也更“图论”。两种方案对比一下算法复杂度代码量思想难度适用性双向最短路枚举边O((nm)logn) 跑两遍略长容易理解有向图时更灵活双状态DijkstraO((nm)logn) 跑一遍较短需要理解状态思想正权图通用我个人推荐主学第二种因为它把“最短路和次短路是相关的”这个动态过程体现得很直观。第一种虽然也好用但总感觉是在用“拼凑”的方式求次短不如第二种更贴近次短路的本质。下面重点展开双状态Dijkstra。3. 双状态Dijkstra的核心原理3.1 状态设计与松弛规则普通的Dijkstra只维护一个数组dist[i]表示从起点到i的最短路长度。现在要同时维护两个数组dis1[i]从起点1到i的最短路长度dis2[i]从起点1到i的严格次短路长度。初始化的时候dis1[1]0其余dis1为INFdis2数组全部为INF。注意dis2[1]也必须初始化为INF而不是0。因为0是起点的最短路如果让dis2[1]0起点就出现了长度为0的“次短路”后面所有状态都会受到污染。这是很多第一版代码WA掉的原因之一。优先队列里放的是(距离d, 节点u)这样的状态。弹出状态(d,u)后先做一个剪枝如果d大于dis2[u]说明这个状态已经不是u的最短路也不是次短路了直接continue。然后遍历u的所有邻边对每条边(u,v,w)计算新距离nddw。接下来用nd尝试更新v的两个距离。更新规则是如果nd小于dis1[v]说明找到了一个更短的最短路。此时v原来的最短路dis1[v]就“降级”为次短路候选因为它是当前所有非最短路径中最短的一个。具体操作是dis2[v]dis1[v]然后dis1[v]nd并把(nd,v)入队否则如果nd大于dis1[v]且nd小于dis2[v]说明nd虽然不是最短路但可以作为次短路更新dis2[v]nd并把(nd,v)入队。写成代码就是if (nd dis1[v]) { dis2[v] dis1[v]; dis1[v] nd; pq.push({nd, v}); } else if (nd dis1[v] nd dis2[v]) { dis2[v] nd; pq.push({nd, v}); }这里最容易写错的是顺序。一定要先判断能不能更新最短路再把旧最短路降级不能反过来先更新次短路。因为当nd比dis1[v]小时它实际上是“打败了最短路”这时候原最短路自动变成次短路这个继承动作是必须的。如果先执行else ifnd又满足nd小于dis2[v]但没有大于dis1[v]的条件就会漏掉原最短路降级这一步。3.2 为什么这样更新是对的很多人第一遍看这个转移会困惑为什么更新了最短路之后要把旧最短路直接赋给次短路它凭什么是次短路原因很简单在处理到v的这个状态之前dis1[v]一直是从起点到v已知最短的路径。现在出现了一条更短的路径nd那么原来那条dis1[v]就是当前已知的所有非最短路径里最短的。它比之前记录在dis2[v]里的任何候选路径都短因为dis2[v]里的值要么原本就大于等于dis1[v]要么还没有被更新。所以旧最短路确实有资格继承次短路的位置。另一个容易困惑的点是为什么次短路的状态也要入队扩展考虑一条次短路路径1-a-b-...-n它的倒数第二个点b到达终点n用的边并不一定在b的最短路状态中。也就是说到达b时可能是通过“次短路”的方式到的再走一条边到某个中间点接着才汇合到最短路。如果我们只把最短路状态入队这部分次短路前缀就永远无法参与后续松弛。所以Dijkstra队列里不仅要放最短路状态也要放次短路状态这就是双状态的核心。再往深一层说双状态Dijkstra的本质是把“最短路”和“次短路”看成两个层次的状态。Dijkstra按距离从小到大处理状态的性质在这里依然成立。因为边权为正一旦某个状态被弹出它的距离已经不可能再被其它更短路径更新了。我们之所以要额外判断“d大于dis2[u]就continue”是因为同一个点可能以不同的距离多次入队但只有最短路和次短路这两个距离是有意义的其它距离既不会对最短路有贡献也不会成为次短路径的可扩展前缀可以安全丢弃。3.3 复杂度分析与边界细节双状态Dijkstra的时间复杂度依然是O((nm)logn)的量级。虽然每个点可能以“最短路”和“次短路”两种状态分别入队但这两个状态的次数都是有限的整体入队次数仍然和普通Dijkstra同阶。在n5000、m100000的数据范围下用C的priority_queue完全跑得动毫秒级就能出结果。还有几个边界细节值得单独拿出来说。第一无向图必须加双向边。我在对拍时见过有人只存了单向边结果样例侥幸通过一提交就WA。这个问题隐蔽在P2865的数据里因为无向图不加反向边时如果终点恰好能从某个方向到达但另一边正着走才通就会出错。Roadblocks是双向图所以建图时a到b和b到a都要加进去。第二优先队列的排序。C的priority_queue默认是大顶堆如果要按距离从小到大取出状态需要把它们存成pairint,int后使用greater比较器或者自定义结构体重载大于号。如果不处理这个队列每次弹出的是最大距离整个Dijkstra就废了大概率会TLE或WA。第三重复边和重边。图中可能出现两点之间有多条不同权值的边。用邻接表存边时这些边都会参与松弛算法天然能处理不需要额外去重。反而如果手贱把重边合并成一条可能导致某个更优的次短路方案消失。4. AC代码与避坑指南4.1 完整C实现下面给出一份可以直接AC P2865的C代码关键位置都加了注释。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; struct Edge { int to, w; }; struct State { int d, u; bool operator(const State other) const { return d other.d; } }; int n, r; vectorEdge g[5005]; int dis1[5005], dis2[5005]; int main() { scanf(%d%d, n, r); for (int i 1; i r; i) { int a, b, d; scanf(%d%d%d, a, b, d); g[a].push_back({b, d}); g[b].push_back({a, d}); } memset(dis1, 0x3f, sizeof(dis1)); memset(dis2, 0x3f, sizeof(dis2)); priority_queueState, vectorState, greaterState pq; dis1[1] 0; pq.push({0, 1}); while (!pq.empty()) { State cur pq.top(); pq.pop(); int d cur.d; int u cur.u; if (d dis2[u]) continue; for (const Edge e : g[u]) { int v e.to; int w e.w; int nd d w; if (nd dis1[v]) { dis2[v] dis1[v]; dis1[v] nd; pq.push({nd, v}); } else if (nd dis1[v] nd dis2[v]) { dis2[v] nd; pq.push({nd, v}); } } } printf(%d\n, dis2[n]); return 0; }这里用结构体State定义了优先队列的排序方式。也可以直接用pairint,intfirst是距离second是节点写法更短。两种方式没有本质区别选自己顺手的。4.2 高频陷阱逐一说明这道题提交一两次就AC的人不多很多人卡了半个下午。我整理了几个最典型的坑按出现频率排个优先级。现象原因解决办法输出与样例不一致甚至输出INFdis2[1]被初始化成0把dis2整个初始化为INF包括起点输出和最短路长度一样把nddis1[v]的情况也算进了次短路或者忘了判断严格大于else if里必须写nd dis1[v] nd dis2[v]某个点的最短路更新后次短路没有继承更新顺序写反先更新了dis2后更新dis1必须先处理nd dis1[v]再处理else if队列弹出状态后用d dis1[u]作为跳过条件把普通Dijkstra的写法直接搬过来导致次短路状态被丢弃跳过条件改成d dis2[u]样例过了但全WA无向图只建了单向边检查建图部分两条边都要加运行超时优先队列用成了默认大顶堆每次弹出最大距离改用greater比较器或自定义operator这里我想特别强调“跳过条件”这个坑。普通Dijkstra的写法是if (d ! dis1[u]) continue;或者if (d dis1[u]) continue;放到这道题里如果你只是把dis1[u]换成dis2[u]写成if (d dis2[u]) continue;那是对的。但如果你写成if (d dis1[u] d dis2[u])虽然逻辑上也不算错但间接增加了复杂度而且容易在调试时把自己搞糊涂。规范做法就是判断它是否大于当前节点的次短路距离大于就没必要扩展了。还有一个细节我在本地测试时踩过当更新最短路时如果旧的最短路恰好是INF执行dis2[v] dis1[v]会把INF赋给dis2[v]这没有影响因为INF本来就是当前值。但如果你在初始化时把dis2全部设为0x3f3f3f3f而dis1[v]是INF赋值后dis2[v]也还是INF不会产生错误。真正危险的是把dis2[1]误设为0所以初始化部分一定要用memset。4.3 对拍与验证方法很多同学觉得代码逻辑理清了样例也能过就可以提交了。但次短路这个写法样例太弱经常藏雷。我个人的习惯是至少做一个随机小图对拍专门验证这种带状态的Dijkstra。对拍方法很简单写一个暴力程序固定n从2到8随机生成无向连通图边权随机取1到20。暴力程序怎么求严格次短路最简单可靠的方式是枚举所有“可能路径”。n很小可以用DFS递归记录当前节点和当前距离要求不能重复经过节点注意题目允许重复经过节点但正权图上最优次短路一定不会出现环因为正环只会让路径变长。所以DFS枚举无环路径就可以找到所有值得考虑的路径。把所有从1到n的简单路径长度收集起来排序后找严格大于最短路的那个最小值就是正确答案。然后对同一组数据分别跑双状态Dijkstra和暴力DFS对比输出。随机生成几百组如果结果完全一致代码基本就稳了。这个方法对绝大多数图论题的调试都通用重点是让你从“相信自己写对了”变成“用数据证明你写对了”。在本地对拍的基础上再提交洛谷。如果WA大概率是边界数据触发了某个坑比如等长最短路、重边、起点的次短路污染。这时候不要急着乱改先回到对拍环境把题目样例之外的特殊数据加进测试集比如两点两条边、完全图、链状图等能更快定位问题。5. 从P2865出发的延伸5.1 非严格次短路与第K短路把“严格次短路”搞懂之后可以顺便想想两个变体。第一个变体是“非严格次短路”也就是允许次短路和最短路长度相等比如两条等长的不同最短路我们希望第二条也算“次短”。双状态Dijkstra在这种情况下会遇到一个问题当nd dis1[v]时我们无法从距离上判断这是同一条路径还是另一条等长路径。如果简单地让nd dis2[v]时更新dis2那起点处dis2[1]会被0污染整个算法就崩了。非严格版本通常需要额外记录到每个点的最短路条数或者用两层计数Dijkstra比严格版本麻烦不少。好在USACO原题要的就是严格次短我们的模板正好匹配。第二个变体是真正的第K短路需要用到A*算法或者可持久化堆等进阶技巧。P2865只要求K2而且是最短路和次短路之间的关系所以双状态Dijkstra足够。如果以后遇到“求1到n的第3短、第4短路径”双状态就得扩展成多状态了。在我的实际经验里把P2865做扎实对理解Dijkstra的“状态”这个概念帮助很大。以前写Dijkstradist数组只是记录一个距离做完这道题你会发现优先队列里跑的其实是一堆“路径状态”同一个点可以以多个不同距离的状态存在只是大多数状态在弹出时就被剪枝掉了。这个认知迁移到A*、分层图、动态规划最短路这些话题上都很有用。5.2 一个后续练习方向如果这道题你一次AC了我建议不要急着去刷下一题先花五分钟把前文提到的“双向最短路枚举边”方法也写一遍用同样的对拍脚本验证。理由很现实洛谷上很多次短路、次小生成树类题目题解区两种思路都有人写你至少要能看懂另一种。真正的图论比赛或面试里不一定会限定你只能写双状态Dijkstra有时候另一种方案在有向图上反而更好处理。举例来说Roadblocks是无向图双向最短路不需要建反图但如果换成一个有向图求1到n的次短路枚举边时就必须区分方向第一遍从1跑原图的dis1第二遍从n跑反图的dis2枚举边(u,v)时用dis1[u] w dis2[v]。这个细节如果你只写过无向图版现场容易漏。把两种写法都过一遍下次遇到变体就不会慌。我自己带过不少学算法的人刷USACO系列P2865是Gold组里少见的高性价比题目。代码不长但思想密度高。有人卡了很久最后发现就是把更新顺序写反了或者是dis2[1]初始成了0。这种小坑在赛后总结时往往比AC本身更值钱。刷题不是为了那一个绿勾而是为了下次遇到类似状态设计时能条件反射般避开这些雷。希望这篇细致的拆解能帮你把这块硬骨头顺利啃下来。