Minimum Weighted Subgraph With the Required Paths

Problem

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 theminimum 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.

Examples

Example 1

1
2
3
4
5
6
7
8
9



![](https://assets.leetcode.com/uploads/2022/02/17/example1drawio.png)

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

1
2
3
4
5
6
7
8



![](https://assets.leetcode.com/uploads/2022/02/17/example2-1drawio.png)

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

Solution

Method 1 – Dijkstra’s Algorithm from Multiple Sources

Intuition

To find the minimum subgraph where both src1 and src2 can reach dest, we need to find a node mid such that both sources can reach mid and mid can reach dest. The optimal solution is the minimum sum of shortest paths from src1 to mid, src2 to mid, and mid to dest.

Approach

Build the graph and its reverse (for backward shortest paths).
Use Dijkstra’s algorithm to compute shortest paths:
- From src1 to all nodes.
- From src2 to all nodes.
- From dest to all nodes (using reversed graph).
For each node, sum the three distances. The answer is the minimum sum where all paths exist.
If no such node exists, return -1.

Code

 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 {
public:
    using pii = pair<long long, int>;
    vector<long long> dijkstra(int n, vector<vector<pii>>& graph, int src) {
        vector<long long> dist(n, LLONG_MAX);
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        dist[src] = 0;
        pq.push({0, src});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            for (auto& [v, w] : graph[u]) {
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist;
    }
    int minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
        vector<vector<pii>> g(n), rg(n);
        for (auto& e : edges) {
            g[e[0]].push_back({e[1], e[2]});
            rg[e[1]].push_back({e[0], e[2]});
        }
        auto d1 = dijkstra(n, g, src1);
        auto d2 = dijkstra(n, g, src2);
        auto dd = dijkstra(n, rg, dest);
        long long ans = LLONG_MAX;
        for (int i = 0; i < n; ++i) {
            if (d1[i] == LLONG_MAX || d2[i] == LLONG_MAX || dd[i] == LLONG_MAX) continue;
            ans = min(ans, d1[i] + d2[i] + dd[i]);
        }
        return ans == LLONG_MAX ? -1 : ans;
    }
};

 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


func MinimumWeight(n int, edges [][]int, src1, src2, dest int) int {
    type pair struct{ d, u int }
    dijkstra := func(graph [][][2]int, src int) []int {
        dist := make([]int, n)
        for i := range dist { dist[i] = 1<<60 }
        dist[src] = 0
        pq := &heapPair{}
        heap.Init(pq)
        heap.Push(pq, pair{0, src})
        for pq.Len() > 0 {
            p := heap.Pop(pq).(pair)
            if p.d > dist[p.u] { continue }
            for _, e := range graph[p.u] {
                v, w := e[0], e[1]
                if dist[v] > p.d + w {
                    dist[v] = p.d + w
                    heap.Push(pq, pair{dist[v], v})
                }
            }
        }
        return dist
    }
    graph := make([][][2]int, n)
    rgraph := make([][][2]int, n)
    for _, e := range edges {
        graph[e[0]] = append(graph[e[0]], [2]int{e[1], e[2]})
        rgraph[e[1]] = append(rgraph[e[1]], [2]int{e[0], e[2]})
    }
    d1 := dijkstra(graph, src1)
    d2 := dijkstra(graph, src2)
    dd := dijkstra(rgraph, dest)
    ans := 1<<60
    for i := 0; i < n; i++ {
        if d1[i] == 1<<60 || d2[i] == 1<<60 || dd[i] == 1<<60 { continue }
        sum := d1[i] + d2[i] + dd[i]
        if sum < ans { ans = sum }
    }
    if ans == 1<<60 { return -1 }
    return ans
}
// heapPair implements heap.Interface for pair
type heapPair []pair
func (h heapPair) Len() int { return len(h) }
func (h heapPair) Less(i, j int) bool { return h[i].d < h[j].d }
func (h heapPair) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *heapPair) Push(x interface{}) { *h = append(*h, x.(pair)) }
func (h *heapPair) Pop() interface{} { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }

 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


class Solution {
    public int minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
        List<int[]>[] g = new List[n], rg = new List[n];
        for (int i = 0; i < n; i++) { g[i] = new ArrayList<>(); rg[i] = new ArrayList<>(); }
        for (int[] e : edges) {
            g[e[0]].add(new int[]{e[1], e[2]});
            rg[e[1]].add(new int[]{e[0], e[2]});
        }
        long[] d1 = dijkstra(n, g, src1);
        long[] d2 = dijkstra(n, g, src2);
        long[] dd = dijkstra(n, rg, dest);
        long ans = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (d1[i] == Long.MAX_VALUE || d2[i] == Long.MAX_VALUE || dd[i] == Long.MAX_VALUE) continue;
            ans = Math.min(ans, d1[i] + d2[i] + dd[i]);
        }
        return ans == Long.MAX_VALUE ? -1 : (int)ans;
    }
    private long[] dijkstra(int n, List<int[]>[] g, int src) {
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[src] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{0, src});
        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long d = cur[0]; int u = (int)cur[1];
            if (d > dist[u]) continue;
            for (int[] e : g[u]) {
                int v = e[0], w = e[1];
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }
        return dist;
    }
}

 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


class Solution {
    fun minimumWeight(n: Int, edges: Array<IntArray>, src1: Int, src2: Int, dest: Int): Int {
        fun dijkstra(g: Array<MutableList<Pair<Int, Int>>>, src: Int): LongArray {
            val dist = LongArray(n) { Long.MAX_VALUE }
            val pq = PriorityQueue<Pair<Long, Int>>(compareBy { it.first })
            dist[src] = 0L
            pq.add(0L to src)
            while (pq.isNotEmpty()) {
                val (d, u) = pq.poll()
                if (d > dist[u]) continue
                for ((v, w) in g[u]) {
                    if (dist[v] > d + w) {
                        dist[v] = d + w
                        pq.add(dist[v] to v)
                    }
                }
            }
            return dist
        }
        val g = Array(n) { mutableListOf<Pair<Int, Int>>() }
        val rg = Array(n) { mutableListOf<Pair<Int, Int>>() }
        for (e in edges) {
            g[e[0]].add(e[1] to e[2])
            rg[e[1]].add(e[0] to e[2])
        }
        val d1 = dijkstra(g, src1)
        val d2 = dijkstra(g, src2)
        val dd = dijkstra(rg, dest)
        var ans = Long.MAX_VALUE
        for (i in 0 until n) {
            if (d1[i] == Long.MAX_VALUE || d2[i] == Long.MAX_VALUE || dd[i] == Long.MAX_VALUE) continue
            ans = minOf(ans, d1[i] + d2[i] + dd[i])
        }
        return if (ans == Long.MAX_VALUE) -1 else ans.toInt()
    }
}

 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


import heapq
from typing import List
class Solution:
    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
        def dijkstra(graph, src):
            dist = [float('inf')] * n
            dist[src] = 0
            heap = [(0, src)]
            while heap:
                d, u = heapq.heappop(heap)
                if d > dist[u]: continue
                for v, w in graph[u]:
                    if dist[v] > d + w:
                        dist[v] = d + w
                        heapq.heappush(heap, (dist[v], v))
            return dist
        g = [[] for _ in range(n)]
        rg = [[] for _ in range(n)]
        for u, v, w in edges:
            g[u].append((v, w))
            rg[v].append((u, w))
        d1 = dijkstra(g, src1)
        d2 = dijkstra(g, src2)
        dd = dijkstra(rg, dest)
        ans = float('inf')
        for i in range(n):
            if d1[i] == float('inf') or d2[i] == float('inf') or dd[i] == float('inf'): continue
            ans = min(ans, d1[i] + d2[i] + dd[i])
        return -1 if ans == float('inf') else int(ans)

 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


use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
    pub fn minimum_weighted_subgraph(n: i32, edges: Vec<Vec<i32>>, src1: i32, src2: i32, dest: i32) -> i32 {
        fn dijkstra(n: usize, graph: &Vec<Vec<(usize, i32)>>, src: usize) -> Vec<i64> {
            let mut dist = vec![i64::MAX; n];
            let mut heap = BinaryHeap::new();
            dist[src] = 0;
            heap.push(Reverse((0, src)));
            while let Some(Reverse((d, u))) = heap.pop() {
                if d > dist[u] { continue; }
                for &(v, w) in &graph[u] {
                    if dist[v] > d + w as i64 {
                        dist[v] = d + w as i64;
                        heap.push(Reverse((dist[v], v)));
                    }
                }
            }
            dist
        }
        let n = n as usize;
        let mut g = vec![vec![]; n];
        let mut rg = vec![vec![]; n];
        for e in &edges {
            g[e[0] as usize].push((e[1] as usize, e[2]));
            rg[e[1] as usize].push((e[0] as usize, e[2]));
        }
        let d1 = dijkstra(n, &g, src1 as usize);
        let d2 = dijkstra(n, &g, src2 as usize);
        let dd = dijkstra(n, &rg, dest as usize);
        let mut ans = i64::MAX;
        for i in 0..n {
            if d1[i] == i64::MAX || d2[i] == i64::MAX || dd[i] == i64::MAX { continue; }
            ans = ans.min(d1[i] + d2[i] + dd[i]);
        }
        if ans == i64::MAX { -1 } else { ans as i32 }
    }
}

 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


class Solution {
    minimumWeight(n: number, edges: number[][], src1: number, src2: number, dest: number): number {
        function dijkstra(graph: number[][][], src: number): number[] {
            const dist = Array(n).fill(Infinity);
            dist[src] = 0;
            const heap: [number, number][] = [[0, src]];
            while (heap.length) {
                heap.sort((a, b) => a[0] - b[0]);
                const [d, u] = heap.shift()!;
                if (d > dist[u]) continue;
                for (const [v, w] of graph[u]) {
                    if (dist[v] > d + w) {
                        dist[v] = d + w;
                        heap.push([dist[v], v]);
                    }
                }
            }
            return dist;
        }
        const g: number[][][] = Array.from({length: n}, () => []);
        const rg: number[][][] = Array.from({length: n}, () => []);
        for (const [u, v, w] of edges) {
            g[u].push([v, w]);
            rg[v].push([u, w]);
        }
        const d1 = dijkstra(g, src1);
        const d2 = dijkstra(g, src2);
        const dd = dijkstra(rg, dest);
        let ans = Infinity;
        for (let i = 0; i < n; i++) {
            if (d1[i] === Infinity || d2[i] === Infinity || dd[i] === Infinity) continue;
            ans = Math.min(ans, d1[i] + d2[i] + dd[i]);
        }
        return ans === Infinity ? -1 : ans;
    }
}

Complexity

⏰ Time complexity: O((n + m) log n) — Dijkstra’s algorithm is run three times, each on the graph and its reverse.
🧺 Space complexity: O(n + m) — For graph storage and distance arrays.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Dijkstra’s Algorithm from Multiple Sources#

Intuition#

Approach#

Code#

Complexity#