Minimum Cost to Reach Destination in Time LeetCode solution in Rust

1
impl Solution {
2
  pub fn min_cost(max_time: i32, edges: Vec<Vec<i32>>, passing_fees: Vec<i32>) -> i32 {
3
    fn solve(
4
      dp: &mut Vec<Vec<i32>>,
5
      time: i32,
6
      adj: &Vec<Vec<(i32, i32)>>,
7
      v: i32,
8
      pass: &Vec<i32>,
9
    ) -> i32 {
10
      if time < 0 {
11
        return std::i32::MAX;
12
      }
13
      let n = pass.len() as i32;
14
      if v == n - 1 {
15
        return pass[v as usize];
16
      }
17
      if dp[v as usize][time as usize] != -1 {
18
        return dp[v as usize][time as usize];
19
      }
20
      let mut cost = std::i32::MAX;
21
      for x in &adj[v as usize] {
22
        let u = x.0;
23
        let temp = x.1;
24
        if temp <= time {
25
          let sol = solve(dp, time - temp, adj, u, pass);
26
          cost = cost.min(sol);
27
        }
28
      }
29
      if cost == std::i32::MAX {
30
        dp[v as usize][time as usize] = std::i32::MAX;
31
        return std::i32::MAX;
32
      }
33
      dp[v as usize][time as usize] = cost + pass[v as usize];
34
      dp[v as usize][time as usize]
35
    }
36

37
    let mut dp = vec![vec![-1; 1001]; 1001];
38
    let n = passing_fees.len();
39
    let mut adj = vec![vec![]; n];
40
    for edge in edges.iter() {
41
      let x = edge[0] as usize;
42
      let y = edge[1] as usize;
43
      let time = edge[2];
44
      adj[x].push((y as i32, time));
45
      adj[y].push((x as i32, time));
46
    }
47
    let ans = solve(&mut dp, max_time, &adj, 0, &passing_fees);
48
    if ans == std::i32::MAX {
49
      return -1;
50
    }
51
    ans
52
  }
53
}