#2203
Minimum Weighted Subgraph With the Required Paths
master · 1670 · lc hard +32 · verified · 41.2% accepted · 782 likes · top 21%
Description
You are given an integer n representing the number of nodes in a weighted directed graph, with nodes numbered 0 to n - 1.
You are also given a 2D integer array edges where edges[i] = [fromi, toi, weighti] describes a directed edge from fromi to toi with weight weighti.
Additionally, you are given three distinct integers src1, src2, and dest.
Return the minimum total weight of a subgraph that allows reaching dest from both src1 and src2 via directed paths. If no such subgraph exists, return -1.
A subgraph consists of a subset of the original graph's nodes and edges. Its weight is the sum of the weights of its edges.
Example 1:
Input: 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
Output: 9
Explanation:
The above figure represents the input graph.
The blue edges represent one of the subgraphs that yield the optimal answer.
Note that the subgraph [[1,0,3],[0,5,6]] also yields the optimal answer. It is not possible to get a subgraph with less weight satisfying all the constraints.
Example 2:
Input: n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
Output: -1
Explanation:
The above figure represents the input graph.
It can be seen that there does not exist any path from node 1 to node 2, hence there are no subgraphs satisfying all the constraints.
Code
1
2
3