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*12总成本 5。示例 2输入n 4, edges [[0,2,1],[2,1,1],[1,3,1],[2,3,3]] 输出3 解释不需要反转路径 0→2→1→3 总成本 3。题目约束2 \lt; n \lt; 5 \* 10^41 \lt; edges\.length \lt; 10^50 \lt; ui, vi \lt; n \- 11 \lt; wi \lt; 1000数据量级较大必须使用O((nm)log⁡n)O((nm)\log n)O((nm)logn)的堆优化 Dijkstra暴力解法、分层冗余解法会低效且没必要。二、误区纠正与核心思维突破2.1 常见错误解法避坑很多题解会使用分层图 Dijkstra拆分状态 0/1 记录是否使用开关该解法逻辑正确但代码冗余、常数更大属于过度建模。本题存在数学优化结论可以彻底舍弃状态分层将问题降维为标准单源最短路代码极简、效率最高。2.2 反转操作本质拆解题目开关操作本质对于任意一条原始边u → v, w该边是节点v的入边。当我们到达节点v时可以触发开关将这条入边临时反转为v → u并花费2\*w穿过。等价于原图每一条正向边都可以对应生成一条权重为 2*w 的反向虚拟边。2.3 关键定理本题解题核心定理正权有向图中本题的最优路径一定是简单路径无重复节点、无环。严谨证明本题所有边权w \gt; 0所有路径增量恒为正若一条路径存在环环的总权重一定大于 0删除环后路径总成本更小若原路径环上存在开关操作可将该操作提前至节点第一次访问时执行入边永久存在操作合法因此带环路径一定不是最优解最优解必然是无重复节点的简单路径。2.4 约束自动消除题目限制每个节点开关最多使用一次。最优路径是简单路径每个节点只会被访问一次。单次访问节点最多执行一次开关操作因此题目限制自动满足无需额外状态记录三、最终建模方案基于上述定理问题直接转化为标准单源最短路问题保留原图所有正向边u→v, w正常行走无需开关对每条原图边u→v, w新增一条虚拟反向边v→u, 2\*w代表在v节点使用开关反转入边在新图上跑 Dijkstra起点 0终点 n-1得到的最短路即为答案。四、算法执行步骤初始化长度为 n 的邻接表遍历所有原始边同时添加正向真实边、反向虚拟反转边初始化距离数组为无穷大起点距离置0小根堆实现 Dijkstra 松弛操作正权图可提前返回终点结果最终判断终点是否可达返回对应结果。五、完整代码实现最优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初始化INF10**18dist[INF]*n dist[0]0heap[(0,0)]whileheap:cur_cost,cur_nodeheapq.heappop(heap)# 过期松弛状态直接跳过ifcur_costdist[cur_node]:continue# 正权图首次弹出终点即为最短路提前返回优化效率ifcur_noden-1:returncur_cost# 遍历所有邻边松弛fornxt_node,weightinadj[cur_node]:new_costcur_costweightifnew_costdist[nxt_node]:dist[nxt_node]new_cost heapq.heappush(heap,(new_cost,nxt_node))# 终点不可达return-15.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))# 初始化最短路距离取极大值避免溢出INF10**18min_dist[INF]*n min_dist[0]0# 起点0距离为0# 最小堆(当前累计花费, 当前节点)priority_queue[(0,0)]whilepriority_queue:current_cost,nodeheapq.heappop(priority_queue)# 剪枝当前记录的距离已经更优跳过无效状态ifcurrent_costmin_dist[node]:continue# Dijkstra正权特性首次弹出终点即为最优解提前返回ifnoden-1:returncurrent_cost# 松弛所有邻接边forneighbor,weightingraph[node]:total_costcurrent_costweight# 更新更优路径iftotal_costmin_dist[neighbor]:min_dist[neighbor]total_cost heapq.heappush(priority_queue,(total_cost,neighbor))# 遍历完成仍未到达终点返回-1return-15.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))INF10**18dist[INF]*n dist[0]0heap[(0,0)]whileheap:d,uheapq.heappop(heap)ifddist[u]:continueifun-1:returndforv,winadj[u]:ifdwdist[v]:dist[v]dw heapq.heappush(heap,(dist[v],v))return-1# 测试用例验证if__name____main__:solSolution()# 示例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, w1我们会自动生成反向虚拟边1→3, w2。最优路径0→1\(3\) \ 1→3\(2\)总成本 5完全匹配题目最优解。示例2复盘原图正向路径0→2→1→3总成本 3优于所有带反转的路径算法直接选取正向最短路。七、复杂度分析时间复杂度O((nm)log⁡n)O((nm)\log n)O((nm)logn)建图O(m)O(m)O(m)每条边生成两条边总边数2m2m2mDijkstra 堆优化每条边松弛一次堆操作复杂度O(log⁡n)O(\log n)O(logn)适配题目10^5级超大数组效率拉满。空间复杂度O(nm)O(nm)O(nm)邻接表存储扩充后的所有边距离数组、堆为线性空间开销。八、面试高频总结与核心考点1. 解题核心精髓本题最大的考点不是图论模板而是思维建模通过正权图无环最优解定理消除题目看似复杂的“节点单次开关限制”将带约束难题转化为裸最短路问题。2. 思维对比笨方法分层图、状态拆分、双重循环、冗余计算巧方法数学证明消约束、扩充边建模、标准Dijkstra秒杀。3. 通用模板迁移所有正权图、单点单次特殊操作的最短路问题均可优先思考最优解是否为简单路径、约束是否可自动消除避免无脑分层。九、易错点汇总❌ 错误反转边权重为w正确应为2\*w❌ 错误为u添加反向边正确应为给原边终点v添加反向边❌ 错误必须分层记录状态正确正权图自动满足单次约束✅ 正确核心反转操作 预先添加高代价反向虚拟边。