2203. 具有所需路径的最小权重子图

Hard

题目描述

给定一个整数 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

示例 2：

输入：n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
输出：-1

约束条件：

3 <= n <= 10^5
0 <= edges.length <= 10^5
edges[i].length == 3
0 <= fromi, toi, src1, src2, dest <= n - 1
fromi != toi
src1、src2 和 dest 两两不同
1 <= weight[i] <= 10^5

解题思路

这道题的关键洞察是：在最优解中，从 src1 和 src2 到 dest 的路径必然会在某个节点汇合，然后共同走完到 dest 的路径。

核心思路：

枚举所有可能的汇合点 mid
对于每个汇合点，计算 src1 → mid + src2 → mid + mid → dest 的总权重
选择权重最小的方案

具体实现：

构建图的邻接表表示
从 src1 出发，使用 Dijkstra 算法计算到所有节点的最短距离
从 src2 出发，使用 Dijkstra 算法计算到所有节点的最短距离
构建反向图，从 dest 出发计算到所有节点的最短距离（等价于所有节点到 dest 的距离）
枚举每个节点作为汇合点，计算总权重并找最小值

时间复杂度优化： 使用优先队列实现的 Dijkstra 算法，单次时间复杂度为 O((V+E)logV)，总体时间复杂度为 O((V+E)logV)。

这种方法确保了我们能找到全局最优解，因为我们考虑了所有可能的汇合点。

代码实现

class Solution {
public:
    long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
        vector<vector<pair<int, long long>>> graph(n);
        vector<vector<pair<int, long long>>> revGraph(n);
        
        for (auto& edge : edges) {
            graph[edge[0]].push_back({edge[1], edge[2]});
            revGraph[edge[1]].push_back({edge[0], edge[2]});
        }
        
        auto dijkstra = [&](int start, const vector<vector<pair<int, long long>>>& g) {
            vector<long long> dist(n, LLONG_MAX);
            priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
            
            dist[start] = 0;
            pq.push({0, start});
            
            while (!pq.empty()) {
                auto [d, u] = pq.top();
                pq.pop();
                
                if (d > dist[u]) continue;
                
                for (auto& [v, w] : g[u]) {
                    if (dist[u] + w < dist[v]) {
                        dist[v] = dist[u] + w;
                        pq.push({dist[v], v});
                    }
                }
            }
            return dist;
        };
        
        vector<long long> dist1 = dijkstra(src1, graph);
        vector<long long> dist2 = dijkstra(src2, graph);
        vector<long long> distFromDest = dijkstra(dest, revGraph);
        
        long long ans = LLONG_MAX;
        for (int i = 0; i < n; i++) {
            if (dist1[i] != LLONG_MAX && dist2[i] != LLONG_MAX && distFromDest[i] != LLONG_MAX) {
                ans = min(ans, dist1[i] + dist2[i] + distFromDest[i]);
            }
        }
        
        return ans == LLONG_MAX ? -1 : ans;
    }
};

class Solution:
    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
        import heapq
        
        graph = [[] for _ in range(n)]
        rev_graph = [[] for _ in range(n)]
        
        for u, v, w in edges:
            graph[u].append((v, w))
            rev_graph[v].append((u, w))
        
        def dijkstra(start, g):
            dist = [float('inf')] * n
            pq = [(0, start)]
            dist[start] = 0
            
            while pq:
                d, u = heapq.heappop(pq)
                if d > dist[u]:
                    continue
                
                for v, w in g[u]:
                    if dist[u] + w < dist[v]:
                        dist[v] = dist[u] + w
                        heapq.heappush(pq, (dist[v], v))
            
            return dist
        
        dist1 = dijkstra(src1, graph)
        dist2 = dijkstra(src2, graph)
        dist_from_dest = dijkstra(dest, rev_graph)
        
        ans = float('inf')
        for i in range(n):
            if dist1[i] != float('inf') and dist2[i] != float('inf') and dist_from_dest[i] != float('inf'):
                ans = min(ans, dist1[i] + dist2[i] + dist_from_dest[i])
        
        return -1 if ans == float('inf') else ans

public class Solution {
    public long MinimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
        var graph = new List<(int, long)>[n];
        var revGraph = new List<(int, long)>[n];
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<(int, long)>();
            revGraph[i] = new List<(int, long)>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add((edge[1], edge[2]));
            revGraph[edge[1]].Add((edge[0], edge[2]));
        }
        
        long[] Dijkstra(int start, List<(int, long)>[] g) {
            var dist = new long[n];
            Array.Fill(dist, long.MaxValue);
            var pq = new PriorityQueue<(long dist, int node), long>();
            
            dist[start] = 0;
            pq.Enqueue((0, start), 0);
            
            while (pq.Count > 0) {
                var (d, u) = pq.Dequeue();
                if (d > dist[u]) continue;
                
                foreach (var (v, w) in g[u]) {
                    if (dist[u] + w < dist[v]) {
                        dist[v] = dist[u] + w;
                        pq.Enqueue((dist[v], v), dist[v]);
                    }
                }
            }
            return dist;
        }
        
        var dist1 = Dijkstra(src1, graph);
        var dist2 = Dijkstra(src2, graph);
        var distFromDest = Dijkstra(dest, revGraph);
        
        long ans = long.MaxValue;
        for (int i = 0; i < n; i++) {
            if (dist1[i] != long.MaxValue && dist2[i] != long.MaxValue && distFromDest[i] != long.MaxValue) {
                ans = Math.Min(ans, dist1[i] + dist2[i] + distFromDest[i]);
            }
        }
        
        return ans == long.MaxValue ? -1 : ans;
    }
}

var minimumWeight = function(n, edges, src1, src2, dest) {
    function dijkstra(graph, start) {
        const dist = new Array(n).fill(Infinity);
        const pq = [[0, start]];
        dist[start] = 0;
        
        while (pq.length > 0) {
            pq.sort((a, b) => a[0] - b[0]);
            const [d, u] = pq.shift();
            
            if (d > dist[u]) continue;
            
            for (const [v, w] of graph[u] || []) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push([dist[v], v]);
                }
            }
        }
        
        return dist;
    }
    
    const graph = Array(n).fill().map(() => []);
    const reverseGraph = Array(n).fill().map(() => []);
    
    for (const [u, v, w] of edges) {
        graph[u].push([v, w]);
        reverseGraph[v].push([u, w]);
    }
    
    const distFromSrc1 = dijkstra(graph, src1);
    const distFromSrc2 = dijkstra(graph, src2);
    const distToDest = dijkstra(reverseGraph, dest);
    
    let minWeight = Infinity;
    
    for (let i = 0; i < n; i++) {
        if (distFromSrc1[i] !== Infinity && distFromSrc2[i] !== Infinity && distToDest[i] !== Infinity) {
            minWeight = Math.min(minWeight, distFromSrc1[i] + distFromSrc2[i] + distToDest[i]);
        }
    }
    
    return minWeight === Infinity ? -1 : minWeight;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O((V + E) log V)，其中 V 是节点数，E 是边数。需要运行 3 次 Dijkstra 算法
空间复杂度	O(V + E)，用于存储图的邻接表和距离数组

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目