LeetCode 3650 这道中等题，光看标题就很有意思：“边反转的最小路径总成本”。我第一反应是，这不就是个最短路问题吗，跑一遍 Dijkstra 不就行了？真动手才发现，难点根本不在于那套模板，而是怎么把“反转一条边”这个操作拆进最短路的建模里，拆对了，代码半小时内能写完；拆不对，样例过完，一提交就漏一堆情况。
这道题大体上是这么回事：一张有向带权图，从起点到终点找一条路径，你可以选择把某条边的方向反转一次，反转要花额外的成本，最后要的是整条路径的“经过边权之和 + 反转成本”的最小值。如果你已经熟练掌握了单源最短路，又想让自己的图论水平往“更灵活的路”上走一步，这道题是个很好的练手素材。我尽量从建模、代码、踩坑三个维度把它讲透，尤其是那个“两次 Dijkstra 预处理 + 枚举关键边”的套路，类似的题换件马甲还能再见到它。
1. 题意建模与手工推演
1.1 把“反转一条边”翻译成路径形状
做题第一步不是看代码，而是先把题面的规则固定下来，不然写着写着就会混。我这里整理一下这道题需要接受的设定：
给定 n 个节点，编号从 0 到 n-1，以及 m 条有向边，每条边用一个三元组(u, v, w)表示：从 u 到 v 有一条单向边，通过它的成本是 w。另外给一个统一的整数reverseCost，表示反转一条边方向的花费。允许的操作是：把某条边u -> v变成v -> u，方向反了之后，这条边的通过成本仍然按 w 算，但反转操作要多付reverseCost。路径总成本等于经过边的 w 之和，再加上，如果这一路上用了反转操作，把对应的 reverseCost 也累加进去。问从 0 到 n-1 的最小总成本是多少，无法到达时返回 -1。
很多第一次看这类题的人会想当然：那我建图的时候，给每条边顺便加一条反向边，权重是w + reverseCost，然后跑最短路不就行了？先别急着这么干，这是最常见的建模误区。因为如果直接加反向边，相当于所有边都天然允许双向走了，题目里“只能反转一条边”的约束就完全丢了。更麻烦的是，一个路径可能在原方向走一次、反方向再走一次，这跟你只反转一条边的规则对不上。
换个角度看，路径经过一条被反转的边时，形状其实是固定的。假设原边是u -> v，你把它反转成v -> u之后，一条合法的完整路径就会长成：
起点 -> ... -> v ->（走反转后的边）-> u -> ... -> 终点
也就是说，这条反转边像一座桥，让你从正向图里能够到达的 v，跳到一个反向图里能够通往终点的 u。整个路径被这条边切成了三段：前面一段在正向图里从起点摸到 v，中间一段是反转边，后面一段在正向图里从 u 到终点。后面所有推导都以这个路径形状为基础。
1.2 一个简单样例，体会“反转有意义”的条件
光说设定有点干，我拿一个自己手搓的样例来跑一遍。假设 n=4，边是下面三条：
0 -> 1，权重 11 -> 2，权重 13 -> 2，权重 13 -> 0，权重 1
再给reverseCost = 1，起点 0，终点 3。
先看不动任何边的情况：从 0 出发只能到 1，然后从 1 到 2，到了 2 之后，2 没有任何出边，终点 3 完全摸不到。所以不反转是无解的。
现在尝试反转一条边。观察边3 -> 2，原始方向是 3 指向 2，反转后变成2 -> 3，正好把我们缺的最后一步补上：0 -> 1 花 1，1 -> 2 花 1，走反转边 2 -> 3 花1 + 1 = 2。总成本是1 + 1 + 2 = 4。
这个样例能让你直观感受到反转的价值：它本质上是在现有的有向骨架里，允许你挑一条边“倒着走一次”，从而打通原本不通的路线。注意走反转边时，成本是w + reverseCost，不是单独付一个反转费，很多初学者这里会算错，把 w 忘了，或者把 reverseCost 乘了边数。
1.3 为什么不能朴素地“加一条反向边”
再深入解释一下 1.1 里说的误区。如果简单地给每条边都加一条反向的候选边，然后把权重设成w + reverseCost，接着在这样一张“双向化”的图上跑最短路，得到的结果会偏小。
原因在于：这条反向候选边在 Dijkstra 的眼里，和原边没有任何约束关系。路径可以先走u -> v，再走v -> u，把一个本来零成本的往返当作正常子路径，这在真实的“只反转一次”规则下是不允许的。因为一旦你反转了一条边，它的原方向就没了，当前图的结构是确定的，而不是两个方向同时存在。更极端的情况是，路径里可能先后用到三条不同边的反向边，这在朴素模型里也都会被允许，从而算出低于真实答案的结果。
所以，单独把“反转”当操作，而不是当静态路由，才是这题的题眼。
2. 两次 Dijkstra 的建模核心
2.1 预处理正向最短路和反向最短路
既然路径形状被切成了三段，那么自然的想法就是分别预处理三段中“最便宜”的走法。
第一段是“从起点 0 到某个节点 v，在原图上走”，这恰好是单源最短路问题。在原图上从 0 出发跑 Dijkstra，得到数组distS，其中distS[x]表示原图中从 0 到 x 的最小成本。
第二段反转边我们枚举处理，不放进最短路里。
第三段是“从某个节点 u 到终点 n-1，在原图上走”。这看起来还要跑一次多源或多终点的最短路，但关键在于：在一个有向图上，“所有点到终点的最短路”可以等价成“在反向图上从终点出发的单源最短路”。构造一个反向图：原图每条边u -> v变成v -> u，权重不变。然后在反向图上从 n-1 出发跑 Dijkstra，得到distT[u]，它就是原图中从 u 到 n-1 的最短成本。
这里为什么用反向图，我多说一句。原图里你想知道 x 到终点 t 的距离，如果直接对每个 x 各跑一次，复杂度没法看。反向图把边的方向全换了，于是从 t 出发能经过反向边访问的节点，恰好正是原图里能到达 t 的那些节点。距离值也原封不动地保留，因为在反向图上走一条反向边v -> u的代价，就是原图中从 u 到 v 的代价。
2.2 枚举反转边的拼接公式
有了distS和distT，现在对每条原边u -> v（权重 w），假设反转它。反转之后边的方向变成v -> u，通过成本是w + reverseCost，那么一个“完整用到这次反转”的合法路径就是：
0 -> ... -> v花distS[v]
v -> u走反转边，花w + reverseCost
u -> ... -> n-1花distT[u]
三段加起来，总成本：
distS[v] + w + reverseCost + distT[u]
对所有边都算一遍这个值，再和不反转的答案distS[n-1]取最小值，就是最终答案。
注意下标的对应关系：原边是u -> v，反转后从 v 出发到 u，所以distS 看的是 v，distT 看的是 u。这句话我重复三遍都不嫌多，这种下标写反导致的 bug 在编码时极其隐蔽，后面我会专门讲怎么用样例自检。
2.3 为什么这样枚举不会漏解
这一步是很多人写代码时不踏实的地方：我没法证明枚举所有边之后答案就是全局最小，就先写了。其实证明不复杂，用反证法想一想。
假设最优路径 P 确实用到了某条被反转的边 e，原方向为u -> v，反转后从 v 走到 u。路径就能表示成三段：从 0 到 v 的某条原图路径 A，边 e 的反转走法，从 u 到 n-1 的某条原图路径 B。
先看第一段 A。在 A 当中，所有边都是原图中的正常边，所以 A 是一条从 0 到 v 的合法路径，它的成本不可能小于distS[v]，因为distS[v]就是所有这样的路径里最小的一个。如果 A 的成本严格大于distS[v]，那我可以把 A 换成最短路那条，整条路径只会更短，与“P 是最优路径”矛盾。所以 A 的成本必须恰好等于distS[v]，也就是说，最优路径的第一段完全可以用我们预处理的 distS 替代。同理，第三段也必须恰好等于distT[u]。
于是，任何最优解在用到某条反转边 e 时，它的成本必然等于枚举公式里 e 对应的那个总和。枚举所有边时一定会扫到它。用到的反转边只有一条，而没有反转的最优解就被distS[n-1]兜住了。两种可能性覆盖完整，解不丢。
2.4 复杂度分析与适用前提
两次 Dijkstra，每次O(m log n)，枚举 m 条边是O(m)，整体是O(m log n)，空间O(n + m)。
这个复杂度对大图也很友好，顶点和边到十万级都能轻松扛住。适用前提是边权非负。Dijkstra 的贪心正确性建立在非负权边上，如果题目里出现负权重或者负的反转成本，那这套解法就不能用了，得换 Bellman-Ford 或 SPFA，并另行考虑负环，但常规题一般不会这么出。
3. 完整参考实现与细节说明
3.1 Python 参考实现
我先把一份可以直接跑的 Python 实现放出来，再逐段讲关键地方。
import heapq from typing import List class Solution: def minimumTotalCost( self, n: int, edges: List[List[int]], reverseCost: int ) -> int: # 正向图和反向图 graph = [[] for _ in range(n)] rgraph = [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w)) rgraph[v].append((u, w)) INF = 10 ** 18 def dijkstra(g, src): dist = [INF] * n dist[src] = 0 pq = [(0, src)] while pq: d, x = heapq.heappop(pq) if d != dist[x]: continue for y, w in g[x]: nd = d + w if nd < dist[y]: dist[y] = nd heapq.heappush(pq, (nd, y)) return dist # 原图从 0 出发的最短路 distS = dijkstra(graph, 0) # 反向图从 n - 1 出发的最短路 distT = dijkstra(rgraph, n - 1) # 不反转任何边 ans = distS[n - 1] # 枚举每条边反转 for u, v, w in edges: if distS[v] == INF or distT[u] == INF: continue cur = distS[v] + w + reverseCost + distT[u] if cur < ans: ans = cur return -1 if ans >= INF else ans这份代码有几个地方我希望你重视。
第一，dijkstra函数里那个if d != dist[x]: continue。堆里可能留着旧的、大的距离记录，当它被弹出时，dist[x] 已经被更新成了更小的值，所以d != dist[x]时直接跳过，避免重复访问，这也是堆优化 Dijkstra 的标准写法。
第二，回答里 n=1 的边界。如果起点和终点是同一个节点，distS[n-1] = distS[0] = 0，答案就是 0，这个逻辑自动成立。题目如果允许路径长度为零，那没问题；如果不允许，题目一般会给出相应约束，代码层面不用额外判断。
第三，INF选10 ** 18。边权和反转成本叠起来完全可能超过 int32 的范围，Python 大整数无所谓，但如果你转写 C++，一定要用long long并且把 INF 设成4e18级别，避免加法溢出后把 INF 误判成可达值。
3.2 C++ 核心片段参考
C++ 写法的思路完全一致，这里给一个核心的 Dijkstra 函数和最终枚举部分，方便需要性能的读者参考。
const long long INF = 4e18; vector<long long> dijkstra(int n, vector<vector<pair<int, long long>>>& g, int src) { vector<long long> dist(n, INF); priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq; dist[src] = 0; pq.push({0, src}); while (!pq.empty()) { auto [d, x] = pq.top(); pq.pop(); if (d != dist[x]) continue; for (auto [y, w] : g[x]) { if (dist[y] > d + w) { dist[y] = d + w; pq.push({dist[y], y}); } } } return dist; } long long ans = distS[n - 1]; for (auto& e : edges) { int u = e[0], v = e[1]; long long w = e[2]; if (distS[v] == INF || distT[u] == INF) continue; ans = min(ans, distS[v] + w + reverseCost + distT[u]); } return ans >= INF ? -1 : (int)ans;C++ 里最容易翻车的点是INF的选择和加法溢出。有人用INT_MAX当 INF，一旦某个distS[v]是 INF，那么distS[v] + w + reverseCost + distT[u]会直接溢出成负数，然后被min选中，答案变成一个莫名其妙的东西。所以要么每个分支判 INF 再相加，要么把 INF 设置得足够大且用 long long。我习惯两个都做，保险。
3.3 与“分层图”方案的取舍
可能有人想，把“是否已经反转一条边”做成一层状态，建一个两层图：第一层是还没用反转的原始状态，第二层是已经用掉反转的状态，层间连一条“反转边”，然后在分层图上跑最短路。复杂度也是O(m log n)。
但在这道题里，我强烈建议用枚举边的方案，而不是分层图。理由有两个：一是分层图建图逻辑虽然直观，但内存里节点和边都要翻倍，在 m 很大的时候常数开销明显；二是这道题只需要反转一次，枚举全部的“候选反转边”完全足够，分层图解决的是“反转次数上限更大”的通用问题。杀鸡用牛刀，代码还更长，调试成本更高。通用思路我在最后一段展开讲，但那不代表每个题目都要套最重的方案。
4. 边界情况与实测避坑
4.1 不可达与 INF 的坑
如果起点和终点在图里根本不连通，distS[n-1]是 INF，枚举反转边时也可能一条都不满足，最终ans保持 INF，返回 -1。
这里最容易踩的坑是误判。我见过有人用ans == INF判断不可达，但正常 Dijkstra 里 INF 不会变，所以相等没问题。问题出在他们把 INF 设得太小，比如10**9，结果真实答案超过了它，或者加法溢出后把 INF 变成其他值，这时判断就失效了。解决办法很简单：INF 设成当前规模下的一个极大值，比如10**18，判断时用>= INF // 2这种带余量的写法，避免边界精度问题。
4.2 自环、重边与平行边
如果图里出现自环u == v，反转它没有实际意义，方向没变，但公式会给出一个值：distS[u] + w + reverseCost + distT[u]。这相当于在路径里强行插入一个自环再走出来。因为 w 和 reverseCost 都是非负的，这个值永远比distS[u] + distT[u]大，而后者不一定是合法路径，所以它通常不会干扰答案。但万一 reverseCost 是负数，自环就会变成一个可以反复刷的低成本环，导致最短路不存在，这就不是本题的讨论范围了，题目一般声明所有权重非负。
重边更不用担心，每条边是独立的候选反转对象，枚举时多条同方向的边都会各自算一遍，取最小即可。哪怕两条 u 到 v 的边权重不同，反转成本也一样，最终答案自然会挑权重最小的那种走法。
4.3 反转成本为零甚至很小的情况
reverseCost = 0时公式退化成distS[v] + w + distT[u]，等价于允许免费把一条有向边当双向边用一次。这在逻辑上没问题，题目允许免费反转时，答案通常会更小。极端情况下，如果原图已经有一条很短的路，反转一条边反而绕路，那min逻辑会选原路径，不会出错。
唯一需要警惕的是“很小但不为零”的反转成本，比如 reverseCost = 1。此时最优路径里极有可能用上反转边，所以不能为了省事先跑一个“忽略反转”的答案就输出。这个我建议用一组直觉数据自测：把起点周围做一圈“必须绕远路才能到终点”的边，让反转成为唯一方案，验证枚举逻辑拿到的值是不是正确。
4.4 最容易写反的下标：distS[v] 还是 distS[u]
我强调过，原边是u -> v，反转后从 v 到 u。所以路径拼接是distS[v] + w + reverseCost + distT[u]。现实中写反的人非常多，包括我自己第一次写也中招了。
为什么容易反？因为人脑直觉认为“边的起点是 u，那答案里应该有 distS[u]”。但反转后的起点恰恰是 v，因为方向变了。我每次写完这段代码都会顺手拿一个简单样例验证：设一条边0 -> 2权重 5，终点是 2，reverseCost=0。如果下标写反，算出来会变成distS[2] + 5 + 0 + distT[0]，而distT[0]是 0 到 2 的最短路 5，整体等于distS[2] + 10，明显偏大；正确写法是distS[0] + 5 + 0 + distT[2] = 0 + 5 + 0 + 0 = 5。这种样例不用等提交，本地一跑就能纠错。
4.5 强制反转与允许不反转的差别
题面如果写“必须反转一条边”，那答案初始化就不能用distS[n-1]，而应该把所有distS[v] + w + reverseCost + distT[u]的可行值取最小值，如果全是 INF 就返回 -1。本题标题里说的是“边反转的最小路径总成本”，没有强调“必须”，所以按“最多反转一次”处理比较稳妥，也就是取不含反转和含反转的最小值。刷题时一定要先确认清楚题目要求，否则差一行初始化，整个结果都会错。
5. 从这道题看一类图论变体的通用套路
5.1 允许任意次数反转时的退化模型
如果题目改成“可以任意次反转边”，问题反而变简单了：每条边都天然有两条通行方向，原方向成本 w，反方向成本w + reverseCost。因为任意次反转不需要考虑“原方向是否被占用”，每条边只是提供两个可能方向罢了。直接建图：u -> v权重 w，v -> u权重w + reverseCost，然后跑一遍最短路。之前 1.3 里担心的“一条边正反都走”在这里是完全合法的，因为你反转两次又回到原方向，但成本多付了后续反转的费用，最短路不会自找麻烦，所以模型成立。
这给我们一个启示：限制数量的一次性操作，和放开的资源，完全是两种建模难度。放开时直接摊到边上，限制时就得把操作当“状态”或“枚举对象”处理。
5.2 分层图：解决“至多 k 次操作”的通用武器
如果题目扩展成“最多反转 k 条边”，枚举每条边就做不到了，因为组合数爆炸。这时分层图是更通用的解法：建立 k+1 层图，每层保留原图的全部边，层内正常走；层与层之间连“状态转换边”，表示在某层使用一次操作。具体到本题，第 0 层是没用过反转的状态，第 1 层是用过反转的状态。原图边u -> v在第 0 层内建，权重 w；反转边v -> u作为从第 0 层 u（或 v）到第 1 层 v（或 u）的跨层边，权重w + reverseCost。从第 0 层起点出发，终点取第 0 层和第 1 层的终点的较小值。
这个方案的通用性确实很强，但代价是节点数乘 k+1，边数也相应翻倍，运行常数更大。对于 k=1 而且只是枚举所有边就能算尽的情况，枚举法更好写、更好调，面试时也更好讲清楚。
5.3 distS + distT 拼接还有哪些用武之地
最后说一个更高位的套路：当你发现一条路径可以被某个“关键边”切成前后两半，而且关键边本身需要特殊枚举时，最短路预处理正反两遍，然后枚举关键边拼接，几乎是无脑可靠的解法。这个模式在很多题里出现过，比如判断一条边是否属于某对点之间的最短路：如果distS[u] + w + distT[v] == distS[t]，说明这条边在最短路上。再比如找两条最短路相交节点、计算经过某条边的所有最短路计数等等，都是这一个套路的变化。
所以每次做完这种题我都会做一件额外的事：把自己做过的“最短路拼接”题汇总在一起，画一画它们共用的骨架。你会发现刷题刷到后面，图论的难点不是算法模板，而是你能不能把一个操作约束翻译成可枚举的路径形状。能翻译出来，代码只是骨架上的填充。
我个人写这道题时的体会是：别急着敲键盘，先在草稿纸上画几个节点，把可能用到反转边的最优路径手动拆分一下，写出distS[v] + w + reverseCost + distT[u]这个公式，再动手写。整个过程里最耗时间的往往不是 Dijkstra，而是下标写反之后来回怀疑人生。你只要记住一条“反转之后起点是 v、终点是 u”，这道题的核心就抓住了一大半。
