Minimum Weighted Subgraph With the Required Paths LeetCode solution in Rust

1
use std::cmp::Reverse;
2
use std::collections::BinaryHeap;
3

4
impl Solution {
5
  pub fn minimum_weight(n: i32, edges: Vec<Vec<i32>>, src1: i32, src2: i32, dest: i32) -> i64 {
6
    let n = n as usize;
7
    let (mut graph, mut graph_reverse) = (vec![vec![]; n], vec![vec![]; n]);
8
    for e in edges {
9
      let (u, v, w) = (e[0] as usize, e[1] as usize, e[2] as i64);
10
      graph[u].push((v, w));
11
      graph_reverse[v].push((u, w));
12
    }
13

14
    let (mut d1, mut d2, mut d3) = (vec![i64::MAX; n], vec![i64::MAX; n], vec![i64::MAX; n]);
15
    Self::calculate(&graph, &mut d1, src1 as usize);
16
    Self::calculate(&graph, &mut d2, src2 as usize);
17
    Self::calculate(&graph_reverse, &mut d3, dest as usize);
18

19
    let mut ret = i64::MAX;
20
    for u in 0..n {
21
      if d1[u] == i64::MAX || d2[u] == i64::MAX || d3[u] == i64::MAX {
22
        continue;
23
      }
24
      ret = ret.min(d1[u] + d2[u] + d3[u]);
25
    }
26

27
    if ret == i64::MAX {
28
      -1
29
    } else {
30
      ret
31
    }
32
  }
33

34
  fn calculate(graph: &Vec<Vec<(usize, i64)>>, dist: &mut Vec<i64>, src: usize) {
35
    let mut pq = BinaryHeap::new();
36

37
    pq.push(Reverse((0i64, src)));
38
    dist[src] = 0;
39
    while let Some(Reverse((d, u))) = pq.pop() {
40
      if dist[u] < d {
41
        continue;
42
      }
43

44
      for (v, w) in &graph[u] {
45
        let (v, w) = (*v, *w);
46
        if dist[v] <= d + w {
47
          continue;
48
        }
49

50
        dist[v] = d + w;
51
        pq.push(Reverse((d + w, v)));
52
      }
53
    }
54
  }
55
}