LeetCode #2203 — HARD

Minimum Weighted Subgraph With the Required Paths

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

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.

You are also given a 2D integer array edges where edges[i] = [from_i, to_i, weight_i] denotes that there exists a directed edge from from_i to to_i with weight weight_i.

Lastly, you are given three distinct integers src1, src2, and dest denoting three distinct nodes of the graph.

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.

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.

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.

Constraints:

3 <= n <= 10⁵
0 <= edges.length <= 10⁵
edges[i].length == 3
0 <= from_i, to_i, src1, src2, dest <= n - 1
from_i != to_i
src1, src2, and dest are pairwise distinct.
1 <= weight[i] <= 10⁵

Step 01

Brute Force Baseline

Problem summary: 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. 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. Lastly, you are given three distinct integers src1, src2, and dest denoting three distinct nodes of the graph. 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. 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: General problem-solving

Example 1

6
[[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]]
0
1
5

Example 2

3
[[0,1,1],[2,1,1]]
0
1
2

Core Insight

What unlocks the optimal approach

Consider what the paths from src1 to dest and src2 to dest would look like in the optimal solution.
It can be shown that in an optimal solution, the two paths from src1 and src2 will coincide at one node, and the remaining part to dest will be the same for both paths. Now consider how to find the node where the paths will coincide.
How can algorithms for finding the shortest path between two nodes help us?

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #2203: Minimum Weighted Subgraph With the Required Paths
class Solution {
    private static final Long INF = Long.MAX_VALUE;

    public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
        List<Pair<Integer, Long>>[] g = new List[n];
        List<Pair<Integer, Long>>[] rg = new List[n];
        for (int i = 0; i < n; ++i) {
            g[i] = new ArrayList<>();
            rg[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            int f = e[0], t = e[1];
            long w = e[2];
            g[f].add(new Pair<>(t, w));
            rg[t].add(new Pair<>(f, w));
        }
        long[] d1 = dijkstra(g, src1);
        long[] d2 = dijkstra(g, src2);
        long[] d3 = dijkstra(rg, dest);
        long ans = -1;
        for (int i = 0; i < n; ++i) {
            if (d1[i] == INF || d2[i] == INF || d3[i] == INF) {
                continue;
            }
            long t = d1[i] + d2[i] + d3[i];
            if (ans == -1 || ans > t) {
                ans = t;
            }
        }
        return ans;
    }

    private long[] dijkstra(List<Pair<Integer, Long>>[] g, int u) {
        int n = g.length;
        long[] dist = new long[n];
        Arrays.fill(dist, INF);
        dist[u] = 0;
        PriorityQueue<Pair<Long, Integer>> q
            = new PriorityQueue<>(Comparator.comparingLong(Pair::getKey));
        q.offer(new Pair<>(0L, u));
        while (!q.isEmpty()) {
            Pair<Long, Integer> p = q.poll();
            long d = p.getKey();
            u = p.getValue();
            if (d > dist[u]) {
                continue;
            }
            for (Pair<Integer, Long> e : g[u]) {
                int v = e.getKey();
                long w = e.getValue();
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    q.offer(new Pair<>(dist[v], v));
                }
            }
        }
        return dist;
    }
}

// Accepted solution for LeetCode #2203: Minimum Weighted Subgraph With the Required Paths
// Auto-generated Go example from java.
func exampleSolution() {
}
// Reference (java):
// // Accepted solution for LeetCode #2203: Minimum Weighted Subgraph With the Required Paths
// class Solution {
//     private static final Long INF = Long.MAX_VALUE;
// 
//     public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
//         List<Pair<Integer, Long>>[] g = new List[n];
//         List<Pair<Integer, Long>>[] rg = new List[n];
//         for (int i = 0; i < n; ++i) {
//             g[i] = new ArrayList<>();
//             rg[i] = new ArrayList<>();
//         }
//         for (int[] e : edges) {
//             int f = e[0], t = e[1];
//             long w = e[2];
//             g[f].add(new Pair<>(t, w));
//             rg[t].add(new Pair<>(f, w));
//         }
//         long[] d1 = dijkstra(g, src1);
//         long[] d2 = dijkstra(g, src2);
//         long[] d3 = dijkstra(rg, dest);
//         long ans = -1;
//         for (int i = 0; i < n; ++i) {
//             if (d1[i] == INF || d2[i] == INF || d3[i] == INF) {
//                 continue;
//             }
//             long t = d1[i] + d2[i] + d3[i];
//             if (ans == -1 || ans > t) {
//                 ans = t;
//             }
//         }
//         return ans;
//     }
// 
//     private long[] dijkstra(List<Pair<Integer, Long>>[] g, int u) {
//         int n = g.length;
//         long[] dist = new long[n];
//         Arrays.fill(dist, INF);
//         dist[u] = 0;
//         PriorityQueue<Pair<Long, Integer>> q
//             = new PriorityQueue<>(Comparator.comparingLong(Pair::getKey));
//         q.offer(new Pair<>(0L, u));
//         while (!q.isEmpty()) {
//             Pair<Long, Integer> p = q.poll();
//             long d = p.getKey();
//             u = p.getValue();
//             if (d > dist[u]) {
//                 continue;
//             }
//             for (Pair<Integer, Long> e : g[u]) {
//                 int v = e.getKey();
//                 long w = e.getValue();
//                 if (dist[v] > dist[u] + w) {
//                     dist[v] = dist[u] + w;
//                     q.offer(new Pair<>(dist[v], v));
//                 }
//             }
//         }
//         return dist;
//     }
// }

# Accepted solution for LeetCode #2203: Minimum Weighted Subgraph With the Required Paths
class Solution:
    def minimumWeight(
        self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int
    ) -> int:
        def dijkstra(g, u):
            dist = [inf] * n
            dist[u] = 0
            q = [(0, u)]
            while q:
                d, u = heappop(q)
                if d > dist[u]:
                    continue
                for v, w in g[u]:
                    if dist[v] > dist[u] + w:
                        dist[v] = dist[u] + w
                        heappush(q, (dist[v], v))
            return dist

        g = defaultdict(list)
        rg = defaultdict(list)
        for f, t, w in edges:
            g[f].append((t, w))
            rg[t].append((f, w))
        d1 = dijkstra(g, src1)
        d2 = dijkstra(g, src2)
        d3 = dijkstra(rg, dest)
        ans = min(sum(v) for v in zip(d1, d2, d3))
        return -1 if ans >= inf else ans

// Accepted solution for LeetCode #2203: Minimum Weighted Subgraph With the Required Paths
/**
 * [2203] Minimum Weighted Subgraph With the Required Paths
 *
 * 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.
 * 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.
 * Lastly, you are given three distinct integers src1, src2, and dest denoting three distinct nodes of the graph.
 * 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.
 * 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.
 *  
 * Example 1:
 * <img alt="" src="https://assets.leetcode.com/uploads/2022/02/17/example1drawio.png" style="width: 263px; height: 250px;" />
 * 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:
 * <img alt="" src="https://assets.leetcode.com/uploads/2022/02/17/example2-1drawio.png" style="width: 350px; height: 51px;" />
 * 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.
 *
 *  
 * Constraints:
 *
 * 	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, and dest are pairwise distinct.
 * 	1 <= weight[i] <= 10^5
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths/
// discuss: https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn minimum_weight(n: i32, edges: Vec<Vec<i32>>, src1: i32, src2: i32, dest: i32) -> i64 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_2203_example_1() {
        let n = 6;
        let edges = vec![
            vec![0, 2, 2],
            vec![0, 5, 6],
            vec![1, 0, 3],
            vec![1, 4, 5],
            vec![2, 1, 1],
            vec![2, 3, 3],
            vec![2, 3, 4],
            vec![3, 4, 2],
            vec![4, 5, 1],
        ];
        let src1 = 0;
        let src2 = 1;
        let dest = 5;

        let result = 9;

        assert_eq!(Solution::minimum_weight(n, edges, src1, src2, dest), result);
    }

    #[test]
    #[ignore]
    fn test_2203_example_2() {
        let n = 3;
        let edges = vec![vec![0, 1, 1], vec![2, 1, 1]];
        let src1 = 0;
        let src2 = 1;
        let dest = 2;

        let result = -1;

        assert_eq!(Solution::minimum_weight(n, edges, src1, src2, dest), result);
    }
}

// Accepted solution for LeetCode #2203: Minimum Weighted Subgraph With the Required Paths
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #2203: Minimum Weighted Subgraph With the Required Paths
// class Solution {
//     private static final Long INF = Long.MAX_VALUE;
// 
//     public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
//         List<Pair<Integer, Long>>[] g = new List[n];
//         List<Pair<Integer, Long>>[] rg = new List[n];
//         for (int i = 0; i < n; ++i) {
//             g[i] = new ArrayList<>();
//             rg[i] = new ArrayList<>();
//         }
//         for (int[] e : edges) {
//             int f = e[0], t = e[1];
//             long w = e[2];
//             g[f].add(new Pair<>(t, w));
//             rg[t].add(new Pair<>(f, w));
//         }
//         long[] d1 = dijkstra(g, src1);
//         long[] d2 = dijkstra(g, src2);
//         long[] d3 = dijkstra(rg, dest);
//         long ans = -1;
//         for (int i = 0; i < n; ++i) {
//             if (d1[i] == INF || d2[i] == INF || d3[i] == INF) {
//                 continue;
//             }
//             long t = d1[i] + d2[i] + d3[i];
//             if (ans == -1 || ans > t) {
//                 ans = t;
//             }
//         }
//         return ans;
//     }
// 
//     private long[] dijkstra(List<Pair<Integer, Long>>[] g, int u) {
//         int n = g.length;
//         long[] dist = new long[n];
//         Arrays.fill(dist, INF);
//         dist[u] = 0;
//         PriorityQueue<Pair<Long, Integer>> q
//             = new PriorityQueue<>(Comparator.comparingLong(Pair::getKey));
//         q.offer(new Pair<>(0L, u));
//         while (!q.isEmpty()) {
//             Pair<Long, Integer> p = q.poll();
//             long d = p.getKey();
//             u = p.getValue();
//             if (d > dist[u]) {
//                 continue;
//             }
//             for (Pair<Integer, Long> e : g[u]) {
//                 int v = e.getKey();
//                 long w = e.getValue();
//                 if (dist[v] > dist[u] + w) {
//                     dist[v] = dist[u] + w;
//                     q.offer(new Pair<>(dist[v], v));
//                 }
//             }
//         }
//         return dist;
//     }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(1)

Approach Breakdown

BRUTE FORCE

O(n²) time

O(1) space

Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.

OPTIMIZED

O(n) time

O(1) space

Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.

Shortcut: If you are using nested loops on an array, there is almost always an O(n) solution. Look for the right auxiliary state.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.