rustgym 0.2.0

rustgym solutions
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

struct Solution;

use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::i32;

#[derive(Eq, Debug)]
struct State {
    position: usize,
    stop: usize,
    cost: i32,
}

impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}

impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl PartialEq for State {
    fn eq(&self, other: &Self) -> bool {
        self.cost == other.cost
    }
}

#[derive(Copy, Clone)]
struct Edge {
    u: usize,
    v: usize,
    cost: i32,
}

impl Solution {
    fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
        let n = n as usize;
        let src = src as usize;
        let dst = dst as usize;
        let k = k as usize;
        let mut prices = vec![i32::MAX; n];
        prices[src] = 0;
        let mut edges: Vec<Vec<Edge>> = vec![vec![]; n];
        for f in flights {
            let u = f[0] as usize;
            let v = f[1] as usize;
            let cost = f[2];
            edges[u].push(Edge { u, v, cost });
        }
        let mut pq: BinaryHeap<State> = BinaryHeap::new();
        pq.push(State {
            position: src,
            stop: 0,
            cost: 0,
        });
        while let Some(s) = pq.pop() {
            if s.position == dst {
                return s.cost;
            }
            prices[s.position] = i32::min(s.cost, prices[s.position]);
            if s.stop <= k {
                for e in &edges[s.position] {
                    pq.push(State {
                        position: e.v,
                        cost: s.cost + e.cost,
                        stop: s.stop + 1,
                    });
                }
            }
        }
        if prices[dst] == i32::MAX {
            -1
        } else {
            prices[dst]
        }
    }
}

#[test]
fn test() {
    let n = 3;
    let flights = vec![vec![0, 1, 100], vec![1, 2, 100], vec![0, 2, 500]];
    let src = 0;
    let dst = 2;
    let k = 1;
    assert_eq!(Solution::find_cheapest_price(n, flights, src, dst, k), 200);
}