LeetCode 3650. 边反转的最小路径总成本 —— 图论建模与 Dijkstra 最短路（最优思维解）

LeetCode 3650. 边反转的最小路径总成本 —— 图论建模与 Dijkstra 最短路（最优思维解）

一、题目描述

给你一个包含n个节点的有向带权图，节点编号从0到n \- 1。同时给你一个数组edges，其中edges\[i\] = \[ui, vi, wi\]表示一条从节点ui到节点vi的有向边，其成本为wi。

每个节点ui都有一个最多可使用一次的开关：当你到达ui且尚未使用其开关时，你可以对其一条入边vi → ui激活开关，将该边反转为ui → vi并立即穿过它。

核心规则：

• 反转仅对当前单次移动有效，非全局永久反转；

• 使用反转边的固定成本为2 \* wi；

• 每个节点的开关全局最多使用一次。

请你返回从节点0到达节点n \- 1的最小总成本。如果无法到达，返回\-1。

题目示例

示例 1

输入：n = 4, edges = [[0,1,3],[3,1,1],[2,3,4],[0,2,2]] 输出：5 解释：路径 0 → 1（成本3），在节点 1 使用开关反转边 3→1 为 1→3 并穿过（成本2*1=2），总成本 5。

示例 2

输入：n = 4, edges = [[0,2,1],[2,1,1],[1,3,1],[2,3,3]] 输出：3 解释：不需要反转，路径 0→2→1→3 总成本 3。

题目约束

• 2 \<= n \<= 5 \* 10^4

• 1 \<= edges\.length \<= 10^5

• 0 \<= ui, vi \<= n \- 1

• 1 \<= wi \<= 1000

数据量级较大，必须使用O((n+m)log⁡n)O((n+m)\log n)O((n+m)logn)的堆优化 Dijkstra，暴力解法、分层冗余解法会低效且没必要。

二、误区纠正与核心思维突破

2.1 常见错误解法（避坑）

很多题解会使用分层图 Dijkstra（拆分状态 0/1 记录是否使用开关），该解法逻辑正确，但代码冗余、常数更大，属于过度建模。

本题存在数学优化结论，可以彻底舍弃状态分层，将问题降维为标准单源最短路，代码极简、效率最高。

2.2 反转操作本质拆解

题目开关操作本质：

对于任意一条原始边u → v, w，该边是节点v的入边。

当我们到达节点v时，可以触发开关，将这条入边临时反转为v → u，并花费2\*w穿过。

等价于：原图每一条正向边，都可以对应生成一条权重为 2*w 的反向虚拟边。

2.3 关键定理（本题解题核心）

定理：正权有向图中，本题的最优路径一定是简单路径（无重复节点、无环）。

严谨证明：

1. 本题所有边权w \> 0，所有路径增量恒为正；

2. 若一条路径存在环，环的总权重一定大于 0，删除环后路径总成本更小；

3. 若原路径环上存在开关操作，可将该操作提前至节点第一次访问时执行（入边永久存在，操作合法）；

4. 因此带环路径一定不是最优解，最优解必然是无重复节点的简单路径。

2.4 约束自动消除

题目限制：每个节点开关最多使用一次。

最优路径是简单路径，每个节点只会被访问一次。

单次访问节点，最多执行一次开关操作，因此题目限制自动满足，无需额外状态记录！

三、最终建模方案

基于上述定理，问题直接转化为标准单源最短路问题：

1. 保留原图所有正向边u→v, w（正常行走，无需开关）；

2. 对每条原图边u→v, w，新增一条虚拟反向边v→u, 2\*w（代表在v节点使用开关反转入边）；

3. 在新图上跑 Dijkstra，起点 0，终点 n-1，得到的最短路即为答案。

四、算法执行步骤

1. 初始化长度为 n 的邻接表；

2. 遍历所有原始边，同时添加正向真实边、反向虚拟反转边；

3. 初始化距离数组为无穷大，起点距离置0；

4. 小根堆实现 Dijkstra 松弛操作，正权图可提前返回终点结果；

5. 最终判断终点是否可达，返回对应结果。

五、完整代码实现（最优AC版）

5.1 标准提交代码（极简高效）

fromtypingimportListimportheapqclassSolution:defminCost(self,n:int,edges:List[List[int]])->int:# 构建扩充邻接表：正向真实边 + 反向反转虚拟边adj=[[]for_inrange(n)]foru,v,winedges:# 正常正向边，无需开关adj[u].append((v,w))# 反转虚拟边：在v节点使用开关，反转入边，代价2*wadj[v].append((u,2*w))# Dijkstra初始化INF=10**18dist=[INF]*n dist[0]=0heap=[(0,0)]whileheap:cur_cost,cur_node=heapq.heappop(heap)# 过期松弛状态，直接跳过ifcur_cost>dist[cur_node]:continue# 正权图首次弹出终点即为最短路，提前返回优化效率ifcur_node==n-1:returncur_cost# 遍历所有邻边松弛fornxt_node,weightinadj[cur_node]:new_cost=cur_cost+weightifnew_cost<dist[nxt_node]:dist[nxt_node]=new_cost heapq.heappush(heap,(new_cost,nxt_node))# 终点不可达return-1

5.2 超详细注释版（新手学习）

fromtypingimportListimportheapqclassSolution:defminCost(self,n:int,edges:List[List[int]])->int:# 初始化邻接表，存储扩充后的完整图graph=[[]for_inrange(n)]# 遍历所有原始边，完成图的扩充foru,v,winedges:# 1. 添加原始正向有向边：正常行走，无需开关graph[u].append((v,w))# 2. 添加反转虚拟边：在v节点触发开关，反转u->v入边# 反转行走代价固定为 2 * wgraph[v].append((u,2*w))# 初始化最短路距离，取极大值避免溢出INF=10**18min_dist=[INF]*n min_dist[0]=0# 起点0距离为0# 最小堆：(当前累计花费, 当前节点)priority_queue=[(0,0)]whilepriority_queue:current_cost,node=heapq.heappop(priority_queue)# 剪枝：当前记录的距离已经更优，跳过无效状态ifcurrent_cost>min_dist[node]:continue# Dijkstra正权特性：首次弹出终点即为最优解，提前返回ifnode==n-1:returncurrent_cost# 松弛所有邻接边forneighbor,weightingraph[node]:total_cost=current_cost+weight# 更新更优路径iftotal_cost<min_dist[neighbor]:min_dist[neighbor]=total_cost heapq.heappush(priority_queue,(total_cost,neighbor))# 遍历完成仍未到达终点，返回-1return-1

5.3 全套测试代码（多用例验证）

fromtypingimportListimportheapqclassSolution:defminCost(self,n:int,edges:List[List[int]])->int:adj=[[]for_inrange(n)]foru,v,winedges:adj[u].append((v,w))adj[v].append((u,2*w))INF=10**18dist=[INF]*n dist[0]=0heap=[(0,0)]whileheap:d,u=heapq.heappop(heap)ifd>dist[u]:continueifu==n-1:returndforv,winadj[u]:ifd+w<dist[v]:dist[v]=d+w heapq.heappush(heap,(dist[v],v))return-1# 测试用例验证if__name__=="__main__":sol=Solution()# 示例1print("示例1输出：",sol.minCost(4,[[0,1,3],[3,1,1],[2,3,4],[0,2,2]]))# 5# 示例2print("示例2输出：",sol.minCost(4,[[0,2,1],[2,1,1],[1,3,1],[2,3,3]]))# 3# 无路径测试print("无路径用例输出：",sol.minCost(3,[[0,1,1]]))# -1

六、样例原理深度复盘

示例1复盘

原始边包含3→1, w=1，我们会自动生成反向虚拟边1→3, w=2。

最优路径：0→1\(3\) \+ 1→3\(2\)，总成本 5，完全匹配题目最优解。

示例2复盘

原图正向路径0→2→1→3总成本 3，优于所有带反转的路径，算法直接选取正向最短路。

七、复杂度分析

时间复杂度：O((n+m)log⁡n)O((n+m)\log n)O((n+m)logn)

• 建图：O(m)O(m)O(m)，每条边生成两条边，总边数2m2m2m；

• Dijkstra 堆优化：每条边松弛一次，堆操作复杂度O(log⁡n)O(\log n)O(logn)；

• 适配题目10^5级超大数组，效率拉满。

空间复杂度：O(n+m)O(n+m)O(n+m)

邻接表存储扩充后的所有边，距离数组、堆为线性空间开销。

八、面试高频总结与核心考点

1. 解题核心精髓

本题最大的考点不是图论模板，而是思维建模：

通过正权图无环最优解定理，消除题目看似复杂的“节点单次开关限制”，将带约束难题转化为裸最短路问题。

2. 思维对比

• 笨方法：分层图、状态拆分、双重循环、冗余计算；

• 巧方法：数学证明消约束、扩充边建模、标准Dijkstra秒杀。

3. 通用模板迁移

所有正权图、单点单次特殊操作的最短路问题，均可优先思考：最优解是否为简单路径、约束是否可自动消除，避免无脑分层。

九、易错点汇总

• ❌ 错误：反转边权重为w，正确应为2\*w；

• ❌ 错误：为u添加反向边，正确应为给原边终点v添加反向边；

• ❌ 错误：必须分层记录状态，正确：正权图自动满足单次约束；

• ✅ 正确核心：反转操作 = 预先添加高代价反向虚拟边。