在刷图论题的时候“边反转”三个字一出现我第一反应是上分层图、加状态、搞一个二维 dist。结果做完这道编号 3650 的中等题才发现它真正考的东西其实是建模直觉把“反转”这件事预计算进边权里一次普通 Dijkstra 就收工了。这篇文章我就把完整的思考链路写出来从为什么不需要状态到代码实现再到和“分层图”模型的边界对比。如果你最近在准备算法面试或者打周赛尤其是对图论模型的转换还不太熟的这篇应该能帮你省不少时间。我先把最常见的题面版本概括一下给定 n 个点m 条有向边第 i 条边有一个默认方向和一个正向通行成本 w_i如果你想沿着它的反方向走需要额外花 r_i 的成本把这条边反转。要求从起点 s 到终点 t 的最小总成本输出这个成本不存在路径则输出 -1。注意这里“反转”的成本是按条、按次独立计算的没有任何“最多反转 k 次”的限制。这个细节决定了后面所有算法选择。1. 题目到底在考什么先别急着套最短路模板1.1 一个看似需要状态、其实不需要状态的模型我第一次看到这道题的时候脑子里冒出来的方案是把“当前点”扩成“当前点 当前哪些边被反转了”的复合状态。比如用一个二进制掩码记录已经反转的边集合然后跑 BFS 或者 Dijkstra。这个思路在 m 很小的时候确实可行但 m 一旦到了几十、几百状态空间就是 2^m直接爆炸。所以这题一定藏着一个更简单的结构否则不可能只是中等难度。关键观察其实在“最短路径”本身的性质上只要所有边权非负一条最短路径必然是简单路径也就是说它不会重复经过同一个点更不会反复走过同一条边。因为如果一条路径绕了一圈又回到同一个点把那一段环直接删掉总成本只会更小或者不变。既然每条边在最优路径里最多出现一次那么“反转这条边”这个操作影响范围就只限于你这一次穿越它不会因为你后续又回到某个节点而需要其他边反转来配合。换句话说反转操作在最优路径里没有“后效性”。我花 r_i 反转了边 i走过去了之后我再也不会用到边 i 了那这 r_i 的额外开销就可以直接看作是“从反方向穿过这条边”的代价。1.2 拆边而不是加状态把二选一变成两条弧既然边在路径中最多出现一次那我可以把每条边看成两个独立的候选方向顺着默认方向走成本 w_i先花 r_i 反转再反方向走成本 w_i r_i。于是在建图的时候输入的每一条有向边我都可以拆成两条有向弧默认方向 u → v权值 w_i反向 v → u权值 w_i r_i。这样一来原问题就等价于在这张有 2m 条弧的新图上求 s 到 t 的最短路。因为新图里的每一条弧已经包含了“是否需要反转”的全部成本。后续的 Dijkstra 根本不需要知道这条弧对应的原边是正向还是反转过的反正代价都算在弧权里了。这就是整道题的核心把“遍历边时的方向选择”压缩成“预计算好的弧权”把“操作成本”转化为“路径成本”。1.3 特殊边界零权、负权对拆边法的影响拆边法能够成立的一个隐含前提是边权非负尤其是反转成本 r_i 不能为负数。Dijkstra 的正确性依赖“从堆里弹出的点已经拿到最优距离”这个性质一旦出现负权边就可能存在先走一条负权边、再走一条大正权边最后总成本反而更小的情况堆优化的贪心顺序就会失效。有人可能会问那反转成本 r_i 0 怎么办没问题这时只是出现零权弧Dijkstra 仍然适用最多退化成 0-1 BFS 也能跑但没必要换算法。如果题目真的出现负权反转成本那麻烦就大了因为走一条边再反转回来可能形成负环答案可以无穷小。竞赛题一般会保证所有权值非负遇到这种题如果没给保证反而要怀疑是不是自己理解错了题面。2. 从拆边到 Dijkstra完整建模过程2.1 邻接表怎么建才不容易乱假设输入给的是 u、v、w、r其中 u 到 v 是默认方向w 是顺向成本r 是反转成本。我的邻接表建法是这样// edge 表示一条有向弧 struct Edge { int to; long long cost; }; vectorvectorEdge graph(n); // 输入第 i 条边: u - v, 正向成本 w, 反转成本 r graph[u].push_back({v, w}); // 顺着默认方向走成本 w graph[v].push_back({u, w r}); // 反转后再走等价于从 v 到 u成本 w r这里有个容易出错的地方有些人会把反向弧写成w或者r那都不对。反向穿越的总成本应该是“这条边本身的通行成本 反转成本”也就是w r除非题面描述的是反向有独立的成本 b_i那才直接写成b_i。如果题面给的是无向边并且顺向、反向两个方向的成本分别在输入里写清楚了那就更简单直接加两条弧即可graph[u].push_back({v, cost_u_to_v}); graph[v].push_back({u, cost_v_to_u});我建议在建图阶段就把所有转换做完不要等到 Dijkstra 松弛的时候再去判断方向。松弛阶段保持“拿到一条弧就直接用它更新”的简单逻辑能把出错概率降到最低。2.2 堆优化 Dijkstra 的松弛细节Dijkstra 本身没什么新鲜的但这道题有一个习惯我强烈建议保留用pairlong long, int作为优先队列元素first 是距离second 是节点编号。C 的优先队列默认是大根堆所以要在类型声明上套一层greaterusing P pairlong long, int; priority_queueP, vectorP, greaterP pq;松弛逻辑如下vectorlong long dist(n, INF); dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 陈旧节点跳过 for (const auto e : graph[u]) { if (dist[e.to] d e.cost) { dist[e.to] d e.cost; pq.push({dist[e.to], e.to}); } } }注意if (d ! dist[u]) continue;这行是堆优化 Dijkstra 最常见的性能优化不加也能过但加了之后每个点最多被真正松弛有限次堆里那些“已经被更新过、但后来发现不是最优”的旧记录都能快速跳过。另外提醒一点dist数组一定要用 long long。虽然单条边的成本可能在一个 int 范围内但路径经过很多条边之后累加值很可能超过 2^31 - 1。用 int 存距离大概率会在极端数据上翻车。2.3 手算样例推演光说理论不够直观我拿一个 4 个点的小图完整推一遍。假设边 11 → 2正向成本 2反转成本 5边 22 → 3正向成本 100反转成本 1边 33 → 4正向成本 1反转成本 10。求 1 到 4 的最小成本。拆边之后得到这样几条弧1 → 2成本 22 → 1成本 72 → 3成本 1003 → 2成本 1013 → 4成本 14 → 3成本 11。从 1 出发Dijkstra 跑出来的最优路径是1 → 2成本 2然后从 2 到 3如果顺着默认方向走要 100但如果先反转边 2再走反方向弧 2 → 3 的实际成本其实是“反转成本 1”因为拆边时我们把 2 → 3 反向弧写成了w r 100 1 101等等这里我故意埋了一个容易错的点。让我重新把输入说清楚。边 2 的默认方向是 2 → 3顺向成本 100反转成本 1。那么拆边应该得到2 → 3成本 100顺着默认方向3 → 2成本 100 1 101反转后再从 3 到 2。注意从 2 到 3 已经是默认方向了成本就是 100不存在“先反转再顺着走”这种操作。我刚才说“先反转边 2再走反方向弧 2 → 3 的实际成本是 1”这句话是错的。反转边 2 之后边的方向变成 3 → 2你作为从 2 出发的人走的是 2 → 3方向与反转后的方向还是相反依然不能走。所以从 2 到 3 要么接受 100要么绕路。这个例子很好正好暴露了建图阶段最容易犯的混淆w r到底加在哪条弧上取决于反转之后哪两个点之间可以通行。默认方向是 u → v反转后方向变成 v → u所以“反转后再通行”的形式一定是起点在 v、终点在 u也就是弧 v → u不是 u → v。那我们重新算一个合理的样例。假设边 2 是默认方向 2 → 3顺向成本 100反转成本 1。如果你从 3 到 2不想顺着默认方向逆着走默认方向是 2→3从 3 到 2 本来就逆着需要反转不对我们再理理。输入的定义是默认方向 2 → 3你想从 2 到 3可以顺着走成本 100你想从 3 到 2必须反转成本 1 反转后走总成本 101。所以拆边是2 → 3成本 1003 → 2成本 100 1 101。好现在把 4 个节点的图重新设计得更有讨论价值边 11 默认方向是 2 → 1不行为了路径方向顺一点设 1 → 2成本 2反转成本 5边 2默认方向 3 → 2顺向成本 1反转成本 1。那么从 2 到 3 需要先反转成本 1 1 2不对顺向成本 1 指的是顺着默认方向 3→2 的通行成本反转后方向变成 2→3通行成本应该也是原始通道成本 1再加上反转成本 1总共 2。拆边3 → 2 成本 12 → 3 成本 2。边 3默认方向 3 → 4成本 3反转成本 8。拆边3 → 4 成本 34 → 3 成本 11。这样从 1 到 4 的路径就有对比性了方案 A1 → 22再到 32 → 3 成本 2再到 43 → 4 成本 3总成本 2 2 3 7。 方案 B1 → 22然后 2 → 3 走默认没有 2→3 的默认只有 2→3 反转弧成本 2方案 A 就是最优。我设计这个样例的目的不是给一个多复杂的答案而是为了展示拆边之后每一条弧的权值来源。最终答案是 7。把建表列出来弧成本来源1 → 22边 1 顺向2 → 17边 1 反转后通行3 → 21边 2 默认方向顺向2 → 32边 2 反转成本 通行成本3 → 43边 3 顺向4 → 311边 3 反转后通行Dijkstra 从 1 开始最短就是 1 → 2 → 3 → 4 7。3. 代码实现与踩坑记录3.1 一份可以直接跑的 C 参考实现下面这份代码可以处理单组输入也稍微改一下就能处理多组测试。完整逻辑如下#include bits/stdc.h using namespace std; using ll long long; const ll INF 4e18; struct Edge { int to; ll cost; }; ll dijkstra(int n, int s, int t, const vectorvectorEdge graph) { vectorll dist(n, INF); priority_queuepairll, int, vectorpairll, int, greaterpairll, int pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; if (u t) break; // 提前终止可以省时间但不是必须 for (const Edge e : graph[u]) { if (dist[e.to] d e.cost) { dist[e.to] d e.cost; pq.push({dist[e.to], e.to}); } } } return dist[t] INF ? -1 : dist[t]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s, t; cin n m s t; vectorvectorEdge graph(n); for (int i 0; i m; i) { int u, v, w, r; cin u v w r; // 这里假设输入给的默认方向是 u - v graph[u].push_back({v, w}); // 顺向 graph[v].push_back({u, w r}); // 反转后反向通行 } cout dijkstra(n, s, t, graph) \n; return 0; }如果题目输入给的是无向边加两个方向独立成本那就把graph[u].push_back({v, cost_u_to_v})和graph[v].push_back({u, cost_v_to_u})换成两个独立变量即可。3.2 初始化 INF 与溢出陷阱我见过不少人在 Dijkstra 里用0x3f3f3f3f做 INF那是个 int 范围内的值int 加法不会爆一旦换上 long long 就危险了。两个 0x3f3f3f3f 相加大概是 21 亿还在 int 范围内但路径累加多次之后很容易超过。所以拿 long long 做题时INF 我习惯设置成4e18这样dist[u] e.cost正常不会溢出而且判断dist[t] INF也能区分“不可达”。还有一个细节是优先队列里的d ! dist[u]判断。long long 的比较不受浮点误差影响可以放心用。如果图里存在大量重复松弛这个判断能过滤掉绝大部分陈旧节点堆的大小会控制在合理范围内。3.3 无解情况与多组测试如果dist[t] INF说明从起点遍历不到终点输出 -1。注意题目可能把节点编号从 1 开始你建图时要对输入做--u; --v;转换成 0 基索引不然数组越界直接 RE。多组测试数据时上面代码的graph需要在每组开始前重新构造不能直接复用上一次的节点数据。有些题还允许起点等于终点那种情况初始dist[s] 0输出 0 即可不需要任何边参与。这些边界单独拿出来测一遍基本不会出错。4. 如果题面是“最多反转 k 次”分层图解法与本题的对比4.1 分层图的适用场景把这道题和另一类很像的题放在一起对比会清晰很多。另一类题是这样的你可以对任意边做一次反转操作但整个路径最多允许反转 k 次。注意这时候“反转次数”是一个全局预算不是每条边独立计费。全局预算意味着路径上所有反转操作共享同一个计数上限。拆边法彻底失效因为拆边之后每条弧的反转成本被预计算进去算法根本不知道这条弧消耗了预算也不知道总预算还剩多少。标准解法是分层图。把原图复制成 k1 层编号为 0, 1, ..., k。第 i 层代表“已经使用了 i 次反转”。层内保留原图的所有弧边权不变同时从第 i 层到第 i1 层加一条“跨层弧”表示对当前边做一次反转边权就是反转成本或者题目定义的额外成本。跑 Dijkstra 时每个节点变成二维状态 (点, 层数)终点是所有层里 t 的最小 dist。4.2 为什么拆边法在全局预算下会出错举一个最简单的反例两条边都需要反转但你最多只允许反转 1 次。假设 s → a 的默认方向是 a → ss → t 的默认方向是 t → s你想从 s 到 t必然要同时反转这两条边。拆边法会把两条边的反转成本都算进弧权里最终得到答案 4但实际预算只有 1 次正确结果是不可达或者你只能走出一个不合理的路径。这个问题不是参数设置能规避的是建模维度缺失拆边法的状态空间里根本没有“已经反转了几条”这个维度。所以我在读题的时候一定会先确认一句反转是“每条边随便反转各自计费”还是“所有反转共享一个 k 次上限”。这两者一字之差算法复杂度从 O(m log n) 变成 O(k m log n)完全是两个难度。4.3 一个快速判断的记忆方式我自己总结了一个很粗暴的判断流程遇到“边反转”“边方向”“双向代价不同”这类题时套用如果反转成本以每条边的形式独立出现且路径可以任意选择反穿那先尝试拆边模型最简单如果题目明确写“最多 k 次”“限 k 次”上分层图如果出现“反转后会对后续其他边产生影响”那才是真正的状态压缩模型状态数需要仔细分析通常 m 很小才可做。这个判断流程不止适用于这一道题换到其他“特殊操作”类题目里一样通用比如免费坐一次飞机、免一次罚单、最多绕一次远路本质上都是三种模型之一。5. 比赛中的提速技巧与经验总结5.1 读题后 30 秒内的建模决策我参加过的练习和模拟比赛不少那种“能 A 但想太久”的题最可惜。看到这道题如果 30 秒内没有明确想法我会按下面的顺序快速过一遍能不能把“操作成本”塞进边权里操作是否有全局次数限制原图是否有负权边第一个问题是“拆边”的信号第二个问题是“分层图”的信号第三个问题是“Dijkstra 是否适用”的信号。三次快速判断之后这道题的算法就已经定下来了有向弧 堆优化 Dijkstra代码量在五十行以内。这个判断过程很机械但机械恰恰是它的优势。比赛时候紧张不依赖直觉依赖流程反而更稳。5.2 自测样例怎么选写完代码不要急着提交先跑这几组数据一条边直接反向走验证w r是否计算正确起点等于终点答案应为 0原图存在环验证不会出现重复走边的异常路径不可达的边验证 -1 的输出大边权累加验证 long long 没有爆。其中第二组最容易被人忽略往往题目没明说 s 能不能等于 t但测试数据里就是有。很多选手在 Dijkstra 初始化上没问题答案也会正确输出 0但如果你初始化时不小心给dist[s] INF这里就会挂掉。5.3 从这道题延伸出去的同类模型“边反转”是表面包装内核是“一条边两种通行方式的最短路”。这个内核换个皮就能变成很多题每个城市有高铁和普通火车两种票价求最低出行成本每个字符串操作有正向代价和反向代价求编辑距离每个道路有白天和夜间两种通行成本求最小时间。解法都是同一个思路把状态里的“选择维度”压缩到边权中让 Dijkstra 只在一个维度上跑。比起直接背整个分层图模板我觉得这种“看穿包装”的能力才是刷题真正的收获。我自己在实际练习中最大的体会是遇到“边反转”这类看似需要复杂状态的题先别急着设计二维状态先把边拆开看看。很多中等题考的就是你敢不敢砍状态砍完之后代码量直接少一半也不容易写错。上面这套拆边 Dijkstra 的思路你可以直接拿去套也可以在这个基础上加一些变体练手比如把反转成本改成随路径长度变化或者把最短路换成最小瓶颈路很快就能体会到建模这一步到底值多少分。 
长河君 · 2026/10/14 23:30:07 · 阅读 1.2k 边反转题别再套分层图！拆边法+Dijkstra一举拿下
在刷图论题的时候“边反转”三个字一出现我第一反应是上分层图、加状态、搞一个二维 dist。结果做完这道编号 3650 的中等题才发现它真正考的东西其实是建模直觉把“反转”这件事预计算进边权里一次普通 Dijkstra 就收工了。这篇文章我就把完整的思考链路写出来从为什么不需要状态到代码实现再到和“分层图”模型的边界对比。如果你最近在准备算法面试或者打周赛尤其是对图论模型的转换还不太熟的这篇应该能帮你省不少时间。我先把最常见的题面版本概括一下给定 n 个点m 条有向边第 i 条边有一个默认方向和一个正向通行成本 w_i如果你想沿着它的反方向走需要额外花 r_i 的成本把这条边反转。要求从起点 s 到终点 t 的最小总成本输出这个成本不存在路径则输出 -1。注意这里“反转”的成本是按条、按次独立计算的没有任何“最多反转 k 次”的限制。这个细节决定了后面所有算法选择。1. 题目到底在考什么先别急着套最短路模板1.1 一个看似需要状态、其实不需要状态的模型我第一次看到这道题的时候脑子里冒出来的方案是把“当前点”扩成“当前点 当前哪些边被反转了”的复合状态。比如用一个二进制掩码记录已经反转的边集合然后跑 BFS 或者 Dijkstra。这个思路在 m 很小的时候确实可行但 m 一旦到了几十、几百状态空间就是 2^m直接爆炸。所以这题一定藏着一个更简单的结构否则不可能只是中等难度。关键观察其实在“最短路径”本身的性质上只要所有边权非负一条最短路径必然是简单路径也就是说它不会重复经过同一个点更不会反复走过同一条边。因为如果一条路径绕了一圈又回到同一个点把那一段环直接删掉总成本只会更小或者不变。既然每条边在最优路径里最多出现一次那么“反转这条边”这个操作影响范围就只限于你这一次穿越它不会因为你后续又回到某个节点而需要其他边反转来配合。换句话说反转操作在最优路径里没有“后效性”。我花 r_i 反转了边 i走过去了之后我再也不会用到边 i 了那这 r_i 的额外开销就可以直接看作是“从反方向穿过这条边”的代价。1.2 拆边而不是加状态把二选一变成两条弧既然边在路径中最多出现一次那我可以把每条边看成两个独立的候选方向顺着默认方向走成本 w_i先花 r_i 反转再反方向走成本 w_i r_i。于是在建图的时候输入的每一条有向边我都可以拆成两条有向弧默认方向 u → v权值 w_i反向 v → u权值 w_i r_i。这样一来原问题就等价于在这张有 2m 条弧的新图上求 s 到 t 的最短路。因为新图里的每一条弧已经包含了“是否需要反转”的全部成本。后续的 Dijkstra 根本不需要知道这条弧对应的原边是正向还是反转过的反正代价都算在弧权里了。这就是整道题的核心把“遍历边时的方向选择”压缩成“预计算好的弧权”把“操作成本”转化为“路径成本”。1.3 特殊边界零权、负权对拆边法的影响拆边法能够成立的一个隐含前提是边权非负尤其是反转成本 r_i 不能为负数。Dijkstra 的正确性依赖“从堆里弹出的点已经拿到最优距离”这个性质一旦出现负权边就可能存在先走一条负权边、再走一条大正权边最后总成本反而更小的情况堆优化的贪心顺序就会失效。有人可能会问那反转成本 r_i 0 怎么办没问题这时只是出现零权弧Dijkstra 仍然适用最多退化成 0-1 BFS 也能跑但没必要换算法。如果题目真的出现负权反转成本那麻烦就大了因为走一条边再反转回来可能形成负环答案可以无穷小。竞赛题一般会保证所有权值非负遇到这种题如果没给保证反而要怀疑是不是自己理解错了题面。2. 从拆边到 Dijkstra完整建模过程2.1 邻接表怎么建才不容易乱假设输入给的是 u、v、w、r其中 u 到 v 是默认方向w 是顺向成本r 是反转成本。我的邻接表建法是这样// edge 表示一条有向弧 struct Edge { int to; long long cost; }; vectorvectorEdge graph(n); // 输入第 i 条边: u - v, 正向成本 w, 反转成本 r graph[u].push_back({v, w}); // 顺着默认方向走成本 w graph[v].push_back({u, w r}); // 反转后再走等价于从 v 到 u成本 w r这里有个容易出错的地方有些人会把反向弧写成w或者r那都不对。反向穿越的总成本应该是“这条边本身的通行成本 反转成本”也就是w r除非题面描述的是反向有独立的成本 b_i那才直接写成b_i。如果题面给的是无向边并且顺向、反向两个方向的成本分别在输入里写清楚了那就更简单直接加两条弧即可graph[u].push_back({v, cost_u_to_v}); graph[v].push_back({u, cost_v_to_u});我建议在建图阶段就把所有转换做完不要等到 Dijkstra 松弛的时候再去判断方向。松弛阶段保持“拿到一条弧就直接用它更新”的简单逻辑能把出错概率降到最低。2.2 堆优化 Dijkstra 的松弛细节Dijkstra 本身没什么新鲜的但这道题有一个习惯我强烈建议保留用pairlong long, int作为优先队列元素first 是距离second 是节点编号。C 的优先队列默认是大根堆所以要在类型声明上套一层greaterusing P pairlong long, int; priority_queueP, vectorP, greaterP pq;松弛逻辑如下vectorlong long dist(n, INF); dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 陈旧节点跳过 for (const auto e : graph[u]) { if (dist[e.to] d e.cost) { dist[e.to] d e.cost; pq.push({dist[e.to], e.to}); } } }注意if (d ! dist[u]) continue;这行是堆优化 Dijkstra 最常见的性能优化不加也能过但加了之后每个点最多被真正松弛有限次堆里那些“已经被更新过、但后来发现不是最优”的旧记录都能快速跳过。另外提醒一点dist数组一定要用 long long。虽然单条边的成本可能在一个 int 范围内但路径经过很多条边之后累加值很可能超过 2^31 - 1。用 int 存距离大概率会在极端数据上翻车。2.3 手算样例推演光说理论不够直观我拿一个 4 个点的小图完整推一遍。假设边 11 → 2正向成本 2反转成本 5边 22 → 3正向成本 100反转成本 1边 33 → 4正向成本 1反转成本 10。求 1 到 4 的最小成本。拆边之后得到这样几条弧1 → 2成本 22 → 1成本 72 → 3成本 1003 → 2成本 1013 → 4成本 14 → 3成本 11。从 1 出发Dijkstra 跑出来的最优路径是1 → 2成本 2然后从 2 到 3如果顺着默认方向走要 100但如果先反转边 2再走反方向弧 2 → 3 的实际成本其实是“反转成本 1”因为拆边时我们把 2 → 3 反向弧写成了w r 100 1 101等等这里我故意埋了一个容易错的点。让我重新把输入说清楚。边 2 的默认方向是 2 → 3顺向成本 100反转成本 1。那么拆边应该得到2 → 3成本 100顺着默认方向3 → 2成本 100 1 101反转后再从 3 到 2。注意从 2 到 3 已经是默认方向了成本就是 100不存在“先反转再顺着走”这种操作。我刚才说“先反转边 2再走反方向弧 2 → 3 的实际成本是 1”这句话是错的。反转边 2 之后边的方向变成 3 → 2你作为从 2 出发的人走的是 2 → 3方向与反转后的方向还是相反依然不能走。所以从 2 到 3 要么接受 100要么绕路。这个例子很好正好暴露了建图阶段最容易犯的混淆w r到底加在哪条弧上取决于反转之后哪两个点之间可以通行。默认方向是 u → v反转后方向变成 v → u所以“反转后再通行”的形式一定是起点在 v、终点在 u也就是弧 v → u不是 u → v。那我们重新算一个合理的样例。假设边 2 是默认方向 2 → 3顺向成本 100反转成本 1。如果你从 3 到 2不想顺着默认方向逆着走默认方向是 2→3从 3 到 2 本来就逆着需要反转不对我们再理理。输入的定义是默认方向 2 → 3你想从 2 到 3可以顺着走成本 100你想从 3 到 2必须反转成本 1 反转后走总成本 101。所以拆边是2 → 3成本 1003 → 2成本 100 1 101。好现在把 4 个节点的图重新设计得更有讨论价值边 11 默认方向是 2 → 1不行为了路径方向顺一点设 1 → 2成本 2反转成本 5边 2默认方向 3 → 2顺向成本 1反转成本 1。那么从 2 到 3 需要先反转成本 1 1 2不对顺向成本 1 指的是顺着默认方向 3→2 的通行成本反转后方向变成 2→3通行成本应该也是原始通道成本 1再加上反转成本 1总共 2。拆边3 → 2 成本 12 → 3 成本 2。边 3默认方向 3 → 4成本 3反转成本 8。拆边3 → 4 成本 34 → 3 成本 11。这样从 1 到 4 的路径就有对比性了方案 A1 → 22再到 32 → 3 成本 2再到 43 → 4 成本 3总成本 2 2 3 7。 方案 B1 → 22然后 2 → 3 走默认没有 2→3 的默认只有 2→3 反转弧成本 2方案 A 就是最优。我设计这个样例的目的不是给一个多复杂的答案而是为了展示拆边之后每一条弧的权值来源。最终答案是 7。把建表列出来弧成本来源1 → 22边 1 顺向2 → 17边 1 反转后通行3 → 21边 2 默认方向顺向2 → 32边 2 反转成本 通行成本3 → 43边 3 顺向4 → 311边 3 反转后通行Dijkstra 从 1 开始最短就是 1 → 2 → 3 → 4 7。3. 代码实现与踩坑记录3.1 一份可以直接跑的 C 参考实现下面这份代码可以处理单组输入也稍微改一下就能处理多组测试。完整逻辑如下#include bits/stdc.h using namespace std; using ll long long; const ll INF 4e18; struct Edge { int to; ll cost; }; ll dijkstra(int n, int s, int t, const vectorvectorEdge graph) { vectorll dist(n, INF); priority_queuepairll, int, vectorpairll, int, greaterpairll, int pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; if (u t) break; // 提前终止可以省时间但不是必须 for (const Edge e : graph[u]) { if (dist[e.to] d e.cost) { dist[e.to] d e.cost; pq.push({dist[e.to], e.to}); } } } return dist[t] INF ? -1 : dist[t]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s, t; cin n m s t; vectorvectorEdge graph(n); for (int i 0; i m; i) { int u, v, w, r; cin u v w r; // 这里假设输入给的默认方向是 u - v graph[u].push_back({v, w}); // 顺向 graph[v].push_back({u, w r}); // 反转后反向通行 } cout dijkstra(n, s, t, graph) \n; return 0; }如果题目输入给的是无向边加两个方向独立成本那就把graph[u].push_back({v, cost_u_to_v})和graph[v].push_back({u, cost_v_to_u})换成两个独立变量即可。3.2 初始化 INF 与溢出陷阱我见过不少人在 Dijkstra 里用0x3f3f3f3f做 INF那是个 int 范围内的值int 加法不会爆一旦换上 long long 就危险了。两个 0x3f3f3f3f 相加大概是 21 亿还在 int 范围内但路径累加多次之后很容易超过。所以拿 long long 做题时INF 我习惯设置成4e18这样dist[u] e.cost正常不会溢出而且判断dist[t] INF也能区分“不可达”。还有一个细节是优先队列里的d ! dist[u]判断。long long 的比较不受浮点误差影响可以放心用。如果图里存在大量重复松弛这个判断能过滤掉绝大部分陈旧节点堆的大小会控制在合理范围内。3.3 无解情况与多组测试如果dist[t] INF说明从起点遍历不到终点输出 -1。注意题目可能把节点编号从 1 开始你建图时要对输入做--u; --v;转换成 0 基索引不然数组越界直接 RE。多组测试数据时上面代码的graph需要在每组开始前重新构造不能直接复用上一次的节点数据。有些题还允许起点等于终点那种情况初始dist[s] 0输出 0 即可不需要任何边参与。这些边界单独拿出来测一遍基本不会出错。4. 如果题面是“最多反转 k 次”分层图解法与本题的对比4.1 分层图的适用场景把这道题和另一类很像的题放在一起对比会清晰很多。另一类题是这样的你可以对任意边做一次反转操作但整个路径最多允许反转 k 次。注意这时候“反转次数”是一个全局预算不是每条边独立计费。全局预算意味着路径上所有反转操作共享同一个计数上限。拆边法彻底失效因为拆边之后每条弧的反转成本被预计算进去算法根本不知道这条弧消耗了预算也不知道总预算还剩多少。标准解法是分层图。把原图复制成 k1 层编号为 0, 1, ..., k。第 i 层代表“已经使用了 i 次反转”。层内保留原图的所有弧边权不变同时从第 i 层到第 i1 层加一条“跨层弧”表示对当前边做一次反转边权就是反转成本或者题目定义的额外成本。跑 Dijkstra 时每个节点变成二维状态 (点, 层数)终点是所有层里 t 的最小 dist。4.2 为什么拆边法在全局预算下会出错举一个最简单的反例两条边都需要反转但你最多只允许反转 1 次。假设 s → a 的默认方向是 a → ss → t 的默认方向是 t → s你想从 s 到 t必然要同时反转这两条边。拆边法会把两条边的反转成本都算进弧权里最终得到答案 4但实际预算只有 1 次正确结果是不可达或者你只能走出一个不合理的路径。这个问题不是参数设置能规避的是建模维度缺失拆边法的状态空间里根本没有“已经反转了几条”这个维度。所以我在读题的时候一定会先确认一句反转是“每条边随便反转各自计费”还是“所有反转共享一个 k 次上限”。这两者一字之差算法复杂度从 O(m log n) 变成 O(k m log n)完全是两个难度。4.3 一个快速判断的记忆方式我自己总结了一个很粗暴的判断流程遇到“边反转”“边方向”“双向代价不同”这类题时套用如果反转成本以每条边的形式独立出现且路径可以任意选择反穿那先尝试拆边模型最简单如果题目明确写“最多 k 次”“限 k 次”上分层图如果出现“反转后会对后续其他边产生影响”那才是真正的状态压缩模型状态数需要仔细分析通常 m 很小才可做。这个判断流程不止适用于这一道题换到其他“特殊操作”类题目里一样通用比如免费坐一次飞机、免一次罚单、最多绕一次远路本质上都是三种模型之一。5. 比赛中的提速技巧与经验总结5.1 读题后 30 秒内的建模决策我参加过的练习和模拟比赛不少那种“能 A 但想太久”的题最可惜。看到这道题如果 30 秒内没有明确想法我会按下面的顺序快速过一遍能不能把“操作成本”塞进边权里操作是否有全局次数限制原图是否有负权边第一个问题是“拆边”的信号第二个问题是“分层图”的信号第三个问题是“Dijkstra 是否适用”的信号。三次快速判断之后这道题的算法就已经定下来了有向弧 堆优化 Dijkstra代码量在五十行以内。这个判断过程很机械但机械恰恰是它的优势。比赛时候紧张不依赖直觉依赖流程反而更稳。5.2 自测样例怎么选写完代码不要急着提交先跑这几组数据一条边直接反向走验证w r是否计算正确起点等于终点答案应为 0原图存在环验证不会出现重复走边的异常路径不可达的边验证 -1 的输出大边权累加验证 long long 没有爆。其中第二组最容易被人忽略往往题目没明说 s 能不能等于 t但测试数据里就是有。很多选手在 Dijkstra 初始化上没问题答案也会正确输出 0但如果你初始化时不小心给dist[s] INF这里就会挂掉。5.3 从这道题延伸出去的同类模型“边反转”是表面包装内核是“一条边两种通行方式的最短路”。这个内核换个皮就能变成很多题每个城市有高铁和普通火车两种票价求最低出行成本每个字符串操作有正向代价和反向代价求编辑距离每个道路有白天和夜间两种通行成本求最小时间。解法都是同一个思路把状态里的“选择维度”压缩到边权中让 Dijkstra 只在一个维度上跑。比起直接背整个分层图模板我觉得这种“看穿包装”的能力才是刷题真正的收获。我自己在实际练习中最大的体会是遇到“边反转”这类看似需要复杂状态的题先别急着设计二维状态先把边拆开看看。很多中等题考的就是你敢不敢砍状态砍完之后代码量直接少一半也不容易写错。上面这套拆边 Dijkstra 的思路你可以直接拿去套也可以在这个基础上加一些变体练手比如把反转成本改成随路径长度变化或者把最短路换成最小瓶颈路很快就能体会到建模这一步到底值多少分。