2203-得到要求路径的最小带权子图

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

给你一个整数 n ，它表示一个 带权有向 图的节点数，节点编号为 0 到 n - 1 。

同时给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi, weighti] ，表示从 fromi 到
toi 有一条边权为 weighti 的 有向 边。

最后，给你三个 互不相同 的整数 src1 ，src2 和 dest ，表示图中三个不同的点。

请你从图中选出一个 边权和最小 的子图，使得从 src1 和 src2 出发，在这个子图中，都 可以 到达 dest
。如果这样的子图不存在，请返回 -1 。

子图 中的点和边都应该属于原图的一部分。子图的边权和定义为它所包含的所有边的权值之和。

示例 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]] 也能得到最优解，但无法在满足所有限制的前提下，得到更优解。

示例 2：

**输入：** n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
**输出：** -1
**解释：**
上图为输入的图。
可以看到，不存在从节点 1 到节点 2 的路径，所以不存在任何子图满足所有限制。

提示：

  • 3 <= n <= 105
  • 0 <= edges.length <= 105
  • edges[i].length == 3
  • 0 <= fromi, toi, src1, src2, dest <= n - 1
  • fromi != toi
  • src1 ，src2 和 dest 两两不同。
  • 1 <= weight[i] <= 105

方法一：分析 + 三次最短路

提示 1

边权和最小的子图呈现「Y 型」。

提示 1 解释

首先我们可以知道，在边权和最小的子图中的任意两个点 u 和 v，如果 u 可以到达 v，那么从 u 到 v 一定只有唯一的一条简单路径。这是因为如果存在多条路径，我们也只会走最短的那一条，因此不在最短路径上的那些边都是无意义的，我们可以将它们移除。

这样一来：

  • 从 src}_1 到 dest 有唯一的一条简单路径，记为 X；

  • 从 src}_2 到 dest 有唯一的一条简单路径，记为 Y。

假设 X 上第一个与 Y 共有的节点为 c，显然这样的 c 是一定存在的，因为 dest 就是 X 和 Y 的一个共有节点（但可能存在更早的共有节点）。我们可以断定，从 c 开始到 dest 结束的这一部分，在 X 和 Y 中一定是完全相同的，这是因为 c 到 dest 一定只有唯一的一条简单路径，因此 X 和 Y 必定共有这条路径。因此，整个子图可以看成是三部分的并集：

  • 从 src}_1 到 c 的一条简单路径；

  • 从 src}_2 到 c 的一条简单路径；

  • 从 c 到 dest 的一条简单路径。

此时子图的边权和即为这三部分的边权和之和，即子图呈现「Y 型」。如果 c 与 src}_1，src}_2 或者 dest 中的某个节点重合，那么也是满足要求的。

思路与算法

我们可以枚举 c 来得到边权和最小的子图。此时，我们就需要计算出「从 src}_1 到 c」「从 src}_2 到 c」「从 c 到 dest」这三部分的最短路径。

对于「从 src}_1 到 c」「从 src}_2 到 c」这两部分而言，我们可以使用两次 Dijkstra 算法计算出以 src}_1 为出发点和以 src}_2 为出发点，到所有节点的最短路径长度。而对于「从 c 到 dest」这一部分，我们可以将原图中的所有边反向，这样就变成了「从 dest 到 c」。我们就可以使用 Dijkstra 算法计算出以 dest 为出发点，到所有节点的最短路径长度。

在得到了所有需要的最短路径的长度之后，我们就可以枚举 c 得出答案了。

代码

[sol1-C++]
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
51
52
53
54
class Solution {
public:
    long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
        vector<vector<pair<int, int>>> g(n), grev(n);
        for (const auto& edge: edges) {
            int x = edge[0], y = edge[1], z = edge[2];
            g[x].emplace_back(y, z);
            grev[y].emplace_back(x, z);
        }
        
        auto dijkstra = [&n](const vector<vector<pair<int, int>>>& graph, int start) -> vector<long long> {
            vector<long long> dist(n, -1);
            dist[start] = 0;
            vector<int> used(n);
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
            q.emplace(0, start);
            
            while (!q.empty()) {
                int u = q.top().second;
                q.pop();
                if (used[u]) {
                    continue;
                }
                used[u] = true;
                
                for (const auto& [v, weight]: graph[u]) {
                    long long target = dist[u] + weight;
                    if (dist[v] == -1 || target < dist[v]) {
                        dist[v] = target;
                        q.emplace(dist[v], v);
                    }
                }
            }
            
            return dist;
        };
        
        vector<long long> dist1 = dijkstra(g, src1);
        vector<long long> dist2 = dijkstra(g, src2);
        vector<long long> dist3 = dijkstra(grev, dest);
        
        long long ans = -1;
        for (int i = 0; i < n; ++i) {
            if (dist1[i] != -1 && dist2[i] != -1 && dist3[i] != -1) {
                long long result = dist1[i] + dist2[i] + dist3[i];
                if (ans == -1 || result < ans) {
                    ans = result;
                }
            }
        }
        
        return ans;
    }
};
[sol1-Python3]
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
class Solution:
    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
        g, grev = defaultdict(list), defaultdict(list)
        for (x, y, z) in edges:
            g[x].append((y, z))
            grev[y].append((x, z))
        
        def dijkstra(graph: Dict[int, List[int]], start: int) -> List[int]:
            dist = [-1] * n
            dist[start] = 0
            used = set()
            q = [(0, start)]

            while q:
                u = heapq.heappop(q)[1]
                if u in used:
                    continue
                
                used.add(u)
                for (v, weight) in graph[u]:
                    target = dist[u] + weight
                    if dist[v] == -1 or target < dist[v]:
                        dist[v] = target
                        heapq.heappush(q, (dist[v], v))
            
            return dist
        
        dist1, dist2, dist3 = dijkstra(g, src1), dijkstra(g, src2), dijkstra(grev, dest)
        
        ans = -1
        for i in range(n):
            if dist1[i] != -1 and dist2[i] != -1 and dist3[i] != -1:
                result = dist1[i] + dist2[i] + dist3[i]
                if ans == -1 or result < ans:
                    ans = result
        
        return ans

复杂度分析

  • 时间复杂度：O(n + m \log m)，其中 m 是数组 edges 的长度。

  • 空间复杂度：O(m)，即为存储图和反向图的邻接表需要使用的空间。

 Comments
On this page
2203-得到要求路径的最小带权子图