2203. Minimum Weighted Subgraph With the Required Paths Hard

1/**
2 * [2203] Minimum Weighted Subgraph With the Required Paths
3 *
4 * You are given an integer n denoting the number of nodes of a weighted directed graph. The nodes are numbered from 0 to n - 1.
5 * You are also given a 2D integer array edges where edges[i] = [fromi, toi, weighti] denotes that there exists a directed edge from fromi to toi with weight weighti.
6 * Lastly, you are given three distinct integers src1, src2, and dest denoting three distinct nodes of the graph.
7 * Return the minimum weight of a subgraph of the graph such that it is possible to reach dest from both src1 and src2 via a set of edges of this subgraph. In case such a subgraph does not exist, return -1.
8 * A subgraph is a graph whose vertices and edges are subsets of the original graph. The weight of a subgraph is the sum of weights of its constituent edges.
9 *  
10 * Example 1:
11 * <img alt="" src="https://assets.leetcode.com/uploads/2022/02/17/example1drawio.png" style="width: 263px; height: 250px;" />
12 * 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
13 * Output: 9
14 * Explanation:
15 * The above figure represents the input graph.
16 * The blue edges represent one of the subgraphs that yield the optimal answer.
17 * 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.
18 * 
19 * Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2022/02/17/example2-1drawio.png" style="width: 350px; height: 51px;" />
21 * Input: n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
22 * Output: -1
23 * Explanation:
24 * The above figure represents the input graph.
25 * 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.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	3 <= n <= 10^5
31 * 	0 <= edges.length <= 10^5
32 * 	edges[i].length == 3
33 * 	0 <= fromi, toi, src1, src2, dest <= n - 1
34 * 	fromi != toi
35 * 	src1, src2, and dest are pairwise distinct.
36 * 	1 <= weight[i] <= 10^5
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths/
42// discuss: https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn minimum_weight(n: i32, edges: Vec<Vec<i32>>, src1: i32, src2: i32, dest: i32) -> i64 {
48        
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_2203() {
60    }
61}
62