Leetcode 3650. Minimum Cost Path with Edge Reversals

• Leetcode 3650. Minimum Cost Path with Edge Reversals
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3650. Minimum Cost Path with Edge Reversals

1. 解题思路

这一题思路上就是一个宽度优先的遍历，我们在存储每一条线段的时候都将正负向的线段存储下来，反向的线段的cost无非就是原始权重的两倍，然后我们进行bfs考察到达终点的最优路线即可。

2. 代码实现

给出python代码实现如下：

class Solution:def minCost(self, n: int, edges: List[List[int]]) -> int:graph = defaultdict(list)for u, v, w in edges:graph[u].append((v, w))graph[v].append((u, 2*w))q = [(0, 0)]seen = set()while q:d, u = heapq.heappop(q)if u == n-1:return dif u in seen:continueseen.add(u)for v, w in graph[u]:if v in seen:continueheapq.heappush(q, (d+w, v))return -1

提交代码评测得到：耗时617ms，占用内存74.78MB。