1. 题目到底在考什么建模比写码重要1.1 题意拆解LeetCode 3650这道题标题已经点得很明白边反转的最小路径总成本。但刷题多的朋友肯定有体会LeetCode的标题常常是压缩饼干真正难的不是题目本身而是把压缩的题意还原成我们熟悉的算法模型。这道题的大意是给定一个有向图或者无向图但每条边有方向属性每条边都有一个“正常通行成本”和“反转方向后的成本”。我们需要找一条从起点到终点的路径在路径上可以自由选择某些边按原始方向走、某些边反向走但每次把一条边从原始方向改成反向就要额外支付一次“反转成本”。目标是最小化全程的费用总和。这里要小心一个关键点题目说的是“边反转的最小路径总成本”它问的不是“走一条最短路径”而是“在允许反转边的条件下走一条总成本最小的路径”。也就是说路径允许包含反向边但反转本身要花钱。换句话说普通的最短路算法不能直接套因为边的状态变了一条边能不能走取决于你当前是顺着原方向还是逆着原方向。我第一眼看到这个题脑子里蹦出来的是两个东西一个是《宝石迷阵》里的交换消除另一个是立体车库的升降平移。但仔细一想更准确的类比是你在一张地图上开车有些路是单行道但你可以花钱把某条单行道临时改成双向通行。你从A点到B点要决定改哪几条路最省钱。1.2 为什么这是一道伪装的图论最短路把题意翻译成图论语言本质上是一个带额外状态的最短路问题。每条边本身有两个属性正向成本顺着原始方向走的代价反转成本沿着反方向走的代价当你从节点u走到节点v时如果这条边的原始方向恰好就是u到v那么你支付的是正向成本如果原始方向是v到u你想从u走到v就必须把边反转这时支付的就是反转成本。所以问题变成了每个节点到达时不仅要记录“走到这里花了多少钱”还要记录“你是从哪个方向进入这条边的”——更准确地说你要知道当前在你的路径上最后一条被使用的边到底有没有被反转但这其实不需要因为每次移动都是独立决策。真正的核心是把“每条边可能以两种状态被使用”这个事实转化为图上的状态节点。1.3 最核心的难点不在算法而在状态设计很多人看到“中等难度”就放松了结果一写就卡住。我复盘了一下这题的主要难点有三个第一图的存储方式。有向图的邻接表大家都会写但这里每条边需要同时存正向和反向两个方向的成本如果只是简单存两个方向那反转成本就丢失了。第二状态的定义。什么叫做“当前在某个节点”如果我把每个节点拆成两个状态比如“处于正向到达状态”和“处于反向到达状态”那么这个问题的维度就从N个节点变成2N个节点。第三Dijkstra的松弛逻辑。普通的松弛是dist[v] min(dist[v], dist[u] w)这里两个不同的状态之间可以互相转移需要额外处理。我当时是这么给自己理顺的把原图想象成两层楼第一层楼是“所有边都按正常方向走”的世界第二层楼是“你正走在一条被反转的边上”的世界。从第一层走到第二层需要支付反转成本从第二层回到第一层你走的是正常的正向边。每一层内部都是普通的有向图层与层之间有一条“反转楼梯”。这样建模之后代码就顺了。我把这个方案整理成一套可以直接套用的模板下面详细拆解。2. 三种解法思路对比选对模型代码量差一倍2.1 方案一分层图最推荐分层图是最直观的做法。把原图复制成两层层0表示“上一条使用的边没有被反转”层1表示“上一条使用的边被反转了”。但这里要注意网络上很多分层图教程会写成“层0是原始边、层1是反转边”这种说法其实不够准确容易误导。更严谨的建模方式是这样的对于原图中的每一条有向边 u - v成本 c在层0内部从 u0 到 v0 连一条边权值为 c。这表示上一步没有反转这一步顺着原始方向走状态仍然是不反转。在层1内部从 u1 到 v1 连一条边权值为 c。表示上一步已经处于反转状态这一步继续顺着原始方向走状态保持不变。在层0内部从 u0 到 v1 连一条边权值为 rev_c。表示上一步没有反转这一步要把边反转状态切换到反转层。在层1内部从 u1 到 v0 连一条边权值为 rev_c。表示上一步处于反转状态这一步仍然选择反转边的方向但由于这条边被反转一次后从u走到v就是合法的所以状态切回非反转层。看到这里有朋友可能会问为什么要切来切去我的理解是状态的含义不应该是“这条边本身被反转了”而应该是“你当前这段路径最后一步是不是走了反向”。因为路径是连续的每次走一条边都是独立的决策只要你走的这条边方向与原始方向相反就付一次反转成本方向一致就付正向成本。所以状态只需要记录“上一步是否发生了反转”这个布尔量然后转移时根据当前边的方向决定是否再支付反转成本。如果嫌这个方法复杂还有更简单的表达方式其实就是双状态Dijkstra。2.2 方案二双状态Dijkstra最简洁不建分层图直接维护一个二维的dist数组dist[u][0]到达节点u且最后一条边是顺着原始方向走的最小成本。 dist[u][1]到达节点u且最后一条边是反转后走的最小成本。然后跑Dijkstra在松弛时做状态转移。对每条边u - v正向成本c反转成本rev_c做两次尝试从状态0到状态0dist[v][0] min(dist[v][0], dist[u][0] c)意思是上一步没反转这一步顺着走。从状态0到状态1dist[v][1] min(dist[v][1], dist[u][0] rev_c)意思是上一步没反转这一步反转着走。从状态1到状态0dist[v][0] min(dist[v][0], dist[u][1] c)意思是上一步反转了这一步顺着走。从状态1到状态1dist[v][1] min(dist[v][1], dist[u][1] rev_c)意思是上一步反转了这一步继续反转着走。你仔细观察发现没有这四种转移本质上就是“当前边的两个方向分别作用在两个前置状态上”。写起来一点都不复杂而且根本不需要真的复制一份图代码量比分层的写法少很多。我个人的结论是双状态Dijkstra是这题的最优解思维负担小代码不容易错复杂度也完全在线。2.3 方案三0-1 BFS特判不推荐但值得了解如果题目里所有边的正向成本和反转成本都是0或1那可以直接用0-1 BFS比Dijkstra还要快一个log。但这题不是这个设定所以这里提一句就好不用在这个方向浪费时间。也有人说可以用SPFA我只能说如果是比赛SPFA在负权图上有风险而且这题并没有负权SPFA最坏情况会被卡建议别碰。综合下来我的建议顺序是双状态Dijkstra 分层图 0-1 BFS。下面我会按双状态Dijkstra给出完整代码并且补充一份分层图的建图方式方便大家对比。3. 完整实现与代码讲解从邻接表到AC的全过程3.1 建图细节一个容易踩的坑先看输入是什么样的。一般来说题目会给一个整数n表示节点数量一个二维数组edges表示边每个元素是[u, v, c, rev_c]表示从u到v的正向成本是c如果反向走成本是rev_c。建图时要注意不能把有向边存成无向边。比如edges里只有一条 u-v 的边那么从v到u并不是天然可达的除非你愿意支付rev_c。也就是说邻接表里应该存两条“可走的方向”从u出发走到v支付c标志位为“正向”。从v出发走到u支付rev_c标志位为“反向反转”。这里的第二个方向在使用双状态Dijkstra时其实是作为“从v出发的一条正常边”进入邻接表的。不要被“反转”两个字干扰就把它当作一条普通的出边只是权值不同而已。我见过不少同学在邻接表里只存了一条边然后想着在松弛时再判断要不要反转结果代码越写越乱。正确做法是在建图阶段就把“两个方向”都存成出边并用一个字段标记方向。这个字段不需要参与距离计算只需要在状态转移时决定走到下一个状态时怎么切换。3.2 核心代码Java版本思路通用于所有语言我写的是Java因为面试里遇到图论的频率高Java的数据结构又比较标准。用C的朋友看注释理解后改一下就行。class Solution { public int minimumCost(int n, int[][] edges, int s, int t) { // 邻接表每个元素是 [to, cost, isReverse] // isReverse 0 表示这条出边是按原始方向走的 // isReverse 1 表示这条出边是反转方向走的 Listint[][] graph new List[n]; for (int i 0; i n; i) { graph[i] new ArrayList(); } for (int[] e : edges) { int u e[0], v e[1]; int forward e[2]; // 顺着原始方向 u-v int backward e[3]; // 反转后 v-u 的成本 graph[u].add(new int[]{v, forward, 0}); graph[v].add(new int[]{u, backward, 1}); } // dist[u][0]: 到达u且最后一条边未反转的最小成本 // dist[u][1]: 到达u且最后一条边已反转的最小成本 long[][] dist new long[n][2]; for (int i 0; i n; i) { Arrays.fill(dist[i], Long.MAX_VALUE); } // 起点没有走任何边可以认为“未反转”状态成本为0 // 同时也要初始化反转状态实际上起点出发第一步根据边来决定所以只初始化0状态即可 dist[s][0] 0; PriorityQueuelong[] pq new PriorityQueue((a, b) - Long.compare(a[0], b[0])); pq.offer(new long[]{0, s, 0}); // {cost, node, state} while (!pq.isEmpty()) { long[] cur pq.poll(); long curCost cur[0]; int u (int) cur[1]; int state (int) cur[2]; if (curCost dist[u][state]) continue; // 到达终点即可返回 if (u t) return (int) curCost; for (int[] edge : graph[u]) { int v edge[0]; int w edge[1]; int isRev edge[2]; // 核心状态转移 // 当前状态state 当前边的方向 isRev - 新状态 int newState state ^ isRev; // 相同为0不同为1 long newCost curCost w; if (newCost dist[v][newState]) { dist[v][newState] newCost; pq.offer(new long[]{newCost, v, newState}); } } } return -1; // 不可达 } }这段代码看起来简单但有一个非常容易忽略的细节为什么newState state ^ isRev我解释一下。state表示“上一条使用的边处于什么状态”isRev表示“当前这条边在邻接表里的方向属性”。如果你上一步没有反转现在走的这条边如果也是正向的那么当前边就没有被反转新状态是0如果你上一步没有反转现在走的这条边是反向的那么当前边就发生了反转新状态是1。反过来也一样。所以用异或来合并“上一步状态”和“当前边方向”这两个信息具体来说就是上一步状态与当前边方向是否一致。这个异或写出来之后代码会非常紧凑。但如果不理解背后的含义面试时被问“为什么是异或”容易答不上来。所以我建议在理解层面记清楚状态表示“最后一条边是否反转”每走一条边新状态取决于旧状态和当前边的方向。如果旧状态和当前边方向相同则新状态为0不同则为1。这里注意有一类题的状态是“是否处于某条特殊边上”那个模型里状态切换逻辑不同不要混淆。3.3 复杂度分析这道题的时间瓶颈在哪图有n个节点假设边数为m。在双状态Dijkstra中每个节点会被拆成两种状态所以状态节点总数是2n。每条边在两个方向上都会产生最多两次转移从状态0出发一次、从状态1出发一次所以总松弛次数是O(m)。时间复杂度O((n m) log n)其中log来自优先队列的入队出队。空间复杂度O(n m)dist数组O(n)邻接表O(m)。这个复杂度在LeetCode上跑是毫无压力的即使n到10^5、m到2×10^5也能过。3.4 一个重要的优化终点的提前返回代码里我在取出堆顶节点时如果发现u t就直接返回。这里有一个坑必须是在“第一次弹出时”返回而不是在松弛时发现到达终点就返回。因为Dijkstra的贪心性质保证了某个状态第一次被弹出时它的距离一定是最小的但如果只是在松弛时更新了终点的距离就直接返回那可能还只是暂时的最小值后面可能有更优路径。初学者经常在这里翻车记住“Dijkstra弹出即最优入队不一定最优”这条铁律。4. 易错点与边界用例这些坑我全踩过4.1 坑一把反转成本想当然地加在正向成本上有的同学会想那我不就是求从s到t的最短路然后如果路径里包含反向边就在答案里加上反转成本吗这种想法有问题因为反转成本不是一次性加在路径末尾的它加在每条反向边本身的权值里需要在搜索过程中就参与比较。换句话说反转成本会影响路径选择本身不能在算完最短路之后再事后补贴。举个例子如果有一条边正着走要100反着走要1但反转成本要200。那你纯粹为了走这条边而反转它总成本201非常不划算可如果你绕路要走好几百那反转它反而划算。这种事后的全局权衡只有让反转成本参与搜索才能算对。4.2 坑二忽略“多条边连接同一对节点”的情况题目没说图中每对节点之间只有一条边。如果有多条边从u连到v正向成本、反转成本各自不同建图时直接把所有边都塞进邻接表就行。但要注意在松弛逻辑里不能用if (w dist)这种提前剪枝的方式跳过因为不同的边对应不同的isRev标志可能影响后续的状态转移。正确做法是全部尝试让Dijkstra自己去淘汰。4.3 坑三起点状态只初始化一个我在代码里只给dist[s][0]赋了0dist[s][1]保持无穷大。有人问起点可不可以处于“反转状态”我的理解是起点还没有走过任何边不存在“最后一条边是否反转”这个说法。所以只能把起点当作状态0。如果你把dist[s][1]也赋成0那会凭空多出一些不存在的路径比如在起点先“假装反转一次”再去走普通边答案可能偏小。4.4 边界用例测试我准备了几组用例大家可以拿代码跑一跑验证理解。用例1n2edges[[0,1,5,7]]s0t1。只有一条边正向走成本5反向走成本7。从0到1直接正向走就行答案5。用例2n3edges[[0,1,1,100],[1,2,1,100]]s0t2。最短路是0-1-2成本2不需要反转任何边答案2。用例3n3edges[[0,1,100,1],[1,2,100,1]]s0t2。如果顺着走要200但把两条边都反转就可以0-1反向成本1再从1反向到0不对这里1-2如果从1出发反向走实际上是从2走到1方向的反转但我们要从1到2原始方向是1-2所以顺着走要100反转走要1实际上从1到2反向的意思是走2-1这条原始边的反方向成本为1所以1-2需要1。因此答案是2。你也可以从0先正走到1成本100再从1反走到2成本1总计101不如两条都反向总成本2。用例4n3s0t2edges[[0,1,1,999],[1,2,999,1]]。从0到1正向1再从1到2反向1总成本2比正向绕一圈更优。用例5不可达n3s0t2edges[[0,1,1,1]]根本没有边连到2答案应该是-1或者题目约定的不可达值。这些用例跑通后基本就能确认状态转移逻辑没写错。5. 从这道题提炼出的通用套路状态最短路模板5.1 什么时候该想到“拆状态”刷题多了你会发现有一类最短路题的核心不在图本身而在“状态”。特征如下图上边的可用性和成本与你“怎么走到当前节点”有关。题目里有明显的二元属性比如“是否已使用某个道具”“是否处于冷却期”“是否反转”等。普通Dijkstra的dist数组只记录一维信息无法区分不同状态下的最优值。遇到这三种特征优先考虑把“状态”作为Dijkstra的第二维甚至第三维。写法上就是把dist数组扩展成多维搜索节点也从普通节点变成节点状态的二元组。5.2 这类题的两个变种变种一每个节点最多只能走一次。比如有些题要求路径不能重复经过节点那就不能单纯用Dijkstra得用状压DP因为状态要记录整个路径的访问集合。那个复杂度是指数级的和本题的双状态完全不是一个量级别混。变种二允许在节点上“原地花钱改变状态”。比如走到某个节点时可以花一定成本把后续所有边都变成可双向通行。这其实也是状态最短路只不过状态转移里多了一条“原地自环边”从dist[u][0]转移到dist[u][1]成本为某个固定值。写的时候只需要在松弛循环里额外加一次自环转移即可。变种三边的反转成本不是固定值而是与当前路径长度相关比如“反转次数越多单次成本越高”。这种情况Dijkstra就不适用了因为成本不再是静态的边权需要重新建模多数要用费用流或者动态规划。5.3 我的做题顺序建议如果你在面试或者刷题时遇到这题我建议按这个顺序思考先把题意中的“反转”翻译成“额外成本”确认这是一个最短路问题。思考要不要拆状态。如果题目里存在“上一步状态影响当前选择”的情况就拆。确定状态维度。这题是一维0/1已经是比较简单的情况。建图写转移。优先用双状态Dijkstra别一开始就上分层图。跑边界用例验证。这个顺序看起来简单但很多人在第2步就卡住了总想着改原图的边权结果越改越乱。记住一句话当你在一条边上做文章做不通的时候往往不是边的权值有问题而是你缺少一个维度去描述“边被使用的姿势”。6. 写在最后的一点经验这道题我前后做过不止一次第一次写的时候用了分层图代码接近80行状态转移写到一半自己都绕晕了。后来换成双状态Dijkstra代码直接砍半而且逻辑清晰很多。我现在对这类题的态度是能用状态维度解决的问题绝不复制图能把转移压缩成异或的绝不写四行if。另外还有一个小技巧想分享给大家在调试这种带状态的最短路时不要只打印要答案。把每个状态的dist打印出来用用例3那种小图手动验证很快就能定位是建图问题还是转移问题。我踩过一次坑花了一个小时找Bug最后发现只是邻接表里方向标记写反了。打印状态转移过程一眼就能看出来。如果你把这道题吃透了后面遇到类似“振荡图”“双模式图”“带冷却时间的路径”这类题基本都能直接套用同一个思维模型。这才是刷这题最大的收获。
