Minimum Weighted Subgraph With the Required Paths
HardUpdated: Aug 2, 2025
Practice on:
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
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^50 <= edges.length <= 10^5edges[i].length == 30 <= fromi, toi, src1, src2, dest <= n - 1fromi != toisrc1,src2, anddestare 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
src1to all nodes. - From
src2to all nodes. - From
destto all nodes (using reversed graph).
- From
- 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
C++
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;
}
};
Go
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 }
Java
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;
}
}
Kotlin
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()
}
}
Python
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)
Rust
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 }
}
}
TypeScript
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.