LC 6032. 得到要求路径的最小带权子图
给你一个整数 n ，它表示一个 带权有向 图的节点数，节点编号为 0 到 n - 1 。
同时给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi, weighti] ，表示从 fromi 到 toi 有一条边权为 weighti 的 有向 边。
最后，给你三个 互不相同 的整数 src1 ，src2 和 dest ，表示图中三个不同的点。
请你从图中选出一个 边权和最小 的子图，使得从 src1 和 src2 出发，在这个子图中，都 可以 到达 dest 。如果这样的子图不存在，请返回 -1 。
子图 中的点和边都应该属于原图的一部分。子图的边权和定义为它所包含的所有边的权值之和。
输入：n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5
输出：9
解释：
上图为输入的图。
蓝色边为最优子图之一。
注意，子图 [[1,0,3],[0,5,6]] 也能得到最优解，但无法在满足所有限制的前提下，得到更优解。
思路：dijkstra
- 先算出这三个点（src1、src2、dest）到某个点的距离（以这个点为连接点）
- 然后这三个点的距离就是经过此点后的距离
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
class Solution {
public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
Map<Integer, List<int[]>> g = new HashMap<>(), fg = new HashMap<>();
for (int[] e : edges) {
int f = e[0], t = e[1], v= e[2];
g.putIfAbsent(f, new ArrayList<>());
fg.putIfAbsent(t, new ArrayList<>());
g.get(f).add(new int[]{f, t, v});
fg.get(t).add(new int[]{t, f, v});
}
// 通过 dijkstar 算法得到 src1、src2、dest 到每个点的最短距离
long[] d1 = dijkstra(g, src1, n);
long[] d2 = dijkstra(g, src2, n);
long[] d3 = dijkstra(fg, dest, n);
long ans = Long.MAX_VALUE;
for(int i = 0 ; i < n ; i++){
// 遍历每个点，判断每个点是否能作为连接点
if(d1[i] != -1 && d2[i] != -1 && d3[i] != -1){
ans = Math.min(ans, d1[i] + d2[i] + d3[i]);
}
}
return ans == Long.MAX_VALUE ? -1 : ans;
}
private long[] dijkstra(Map<Integer,List<int[]>> g , int start, int n){
// t[i] 表示从 start 点到 i 的最小距离
long[] t = new long[n];
Arrays.fill(t, -1);
t[start] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b)-> {
return a[2] - b[2] > 0 ? 1 : -1;
});
for(int[] e : g.getOrDefault(start, new ArrayList<>())){
pq.offer(new long[]{e[0] , e[1] , e[2]});
}
while(!pq.isEmpty()){
long[] cur = pq.poll();
if(t[(int)cur[1]] == -1){
t[(int)cur[1]] = cur[2];
for(int[] e : g.getOrDefault((int)cur[1], new ArrayList<>())){
pq.offer(new long[]{e[0], e[1] , cur[2]+e[2]});
}
}
}
return t;
}
}
|