rustgym/leetcode/
_871_minimum_number_of_refueling_stops.rs

1struct Solution;
2
3use std::cmp::Reverse;
4use std::collections::BinaryHeap;
5use std::collections::HashMap;
6
7impl Solution {
8    fn min_refuel_stops(target: i32, start_fuel: i32, mut stations: Vec<Vec<i32>>) -> i32 {
9        let mut queue: BinaryHeap<(Reverse<usize>, usize, i32)> = BinaryHeap::new();
10        stations.push(vec![target, 0]);
11        let n = stations.len();
12        let fuel = start_fuel - stations[0][0];
13        let mut states: HashMap<(usize, usize), i32> = HashMap::new();
14        if fuel >= 0 {
15            states.insert((0, 0), fuel);
16            queue.push((Reverse(0), 0, fuel));
17        }
18        while let Some((Reverse(stop), i, fuel)) = queue.pop() {
19            if i == n - 1 {
20                return stop as i32;
21            }
22            let dist = stations[i + 1][0] - stations[i][0];
23            let take = fuel + stations[i][1] - dist;
24            let skip = fuel - dist;
25            for &(s, f) in &[(stop + 1, take), (stop, skip)] {
26                if f < 0 {
27                    continue;
28                }
29                if let Some(&max_f) = states.get(&(i + 1, s)) {
30                    if max_f >= f {
31                        continue;
32                    }
33                }
34                *states.entry((i + 1, s)).or_default() = f;
35                queue.push((Reverse(s), i + 1, f));
36            }
37        }
38        -1
39    }
40}
41
42#[test]
43fn test() {
44    let target = 1;
45    let start_fuel = 1;
46    let stations = vec_vec_i32![];
47    let res = 0;
48    assert_eq!(
49        Solution::min_refuel_stops(target, start_fuel, stations),
50        res
51    );
52    let target = 100;
53    let start_fuel = 1;
54    let stations = vec_vec_i32![[10, 100]];
55    let res = -1;
56    assert_eq!(
57        Solution::min_refuel_stops(target, start_fuel, stations),
58        res
59    );
60    let target = 100;
61    let start_fuel = 10;
62    let stations = vec_vec_i32![[10, 60], [20, 30], [30, 30], [60, 40]];
63    let res = 2;
64    assert_eq!(
65        Solution::min_refuel_stops(target, start_fuel, stations),
66        res
67    );
68}
rustgym/leetcode/_871_minimum_number_of_refueling_stops.rs

rustgym/leetcode/
_871_minimum_number_of_refueling_stops.rs
