Minimum weighted subgraph with the required paths

Graph Theory Heap (Priority Queue) Shortest Path

41.1% acceptance

Feb 25, 2026

780

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;


impl Solution {
  pub fn minimum_weight(n: i32, edges: Vec<Vec<i32>>, src1: i32, src2: i32, dest: i32) -> i64 {
    let n = n as usize;
    let mut fwd: Vec<Vec<(usize, i64)>> = vec![vec![]; n];
    let mut rev: Vec<Vec<(usize, i64)>> = vec![vec![]; n];
    for e in &edges {
      let (u, v, w) = (e[0] as usize, e[1] as usize, e[2] as i64);
      fwd[u].push((v, w));
      rev[v].push((u, w));
    }
    let dijkstra = |start: usize, adj: &Vec<Vec<(usize, i64)>>| -> Vec<i64> {
      const INF: i64 = i64::MAX / 2;
      let mut dist = vec![INF; n];
      dist[start] = 0;
      let mut heap = BinaryHeap::new();
      heap.push(Reverse((0i64, start)));
      while let Some(Reverse((d, u))) = heap.pop() {
        if d > dist[u] { continue; }
        for &(v, w) in &adj[u] {
          if dist[u] + w < dist[v] {
            dist[v] = dist[u] + w;
            heap.push(Reverse((dist[v], v)));
          }
        }
      }
      dist
    };
    let d1 = dijkstra(src1 as usize, &fwd);
    let d2 = dijkstra(src2 as usize, &fwd);
    let dd = dijkstra(dest as usize, &rev);
    const INF: i64 = i64::MAX / 2;
    let mut ans = INF;
    for v in 0..n {
      if d1[v] < INF && d2[v] < INF && dd[v] < INF {
        ans = ans.min(d1[v] + d2[v] + dd[v]);
      }
    }
    if ans == INF { -1 } else { ans }
  }
}