leetcode:6032. 得到要求路径的最小带权子图

分析：

1.找到一个x st src1 -> x + src2 -> x + x -> dest最小
2.x -> dest 由于x是变得，可以根据反图找到dest到every x 的距离
3.dijk 得到三个dis
4.找到最小的和

ac code

class Solution:def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:# py也来写一下dijkdef dijkstra(g, start):# 初始disdis = [inf] * n# 起点为0dis[start] = 0# 放入到堆中pq = [(0, start)]#开始更新while pq:# 找出最小的disd, x = heappop(pq)# 若已经找到更小的，continue               if dis[x] < d:continue                # 找到和它相邻的节点，更新disfor y, wt in g[x]:new_d = dis[x] + wtif new_d < dis[y]:dis[y] = new_d# 加入更新后的节点，放入堆中heappush(pq, (new_d, y))return dis# 正图g = [[] for _ in range(n)]# 反图rg = [[] for _ in range(n)]# storefor x, y, wt in edges:g[x].append((y, wt))rg[y].append((x, wt))# 得到三个disd1 = dijkstra(g, src1)d2 = dijkstra(g, src2)d3 = dijkstra(rg, dest)# 三个和最小的，找到一个x为交汇点ans = min(sum(d) for d in zip(d1, d2, d3))return ans if ans < inf else -1

总结：

python实现了dijkstra
然后得到单源点到其他点的最短距离
最小带权子图就是找到两条路径的交汇点是的总距离最小
也就是

这个图最短，关键是找到一个合适的x
这就要得到三个dis数组了。。