competitive_library/graph/
shortest_path_faster_algorithm.rs

1//! SPFA
2
3use std::collections::VecDeque;
4
5pub fn spfa(edge: &[Vec<(usize, i64)>], start: usize) -> Option<Vec<i64>> {
6    let mut pending = vec![false; edge.len()];
7    let mut times = vec![0; edge.len()];
8    let mut costs = vec![i64::MAX; edge.len()];
9    let mut q = VecDeque::new();
10    q.push_back(start);
11    times[start] = 1;
12    costs[start] = 0;
13    pending[start] = true;
14
15    while let Some(p) = q.pop_front() {
16        pending[p] = false;
17
18        for &(to, c) in &edge[p] {
19            let cost = costs[p] + c;
20            if costs[to] <= cost {
21                continue;
22            }
23            costs[to] = cost;
24            if !pending[to] {
25                times[to] += 1;
26                if times[to] >= edge.len() {
27                    return None;
28                }
29                pending[to] = true;
30                q.push_back(to);
31            }
32        }
33    }
34
35    Some(costs)
36}
37
38#[cfg(test)]
39mod tests {
40    use super::spfa;
41
42    #[test]
43    fn test_spfa() {
44        let graph = vec![
45            vec![(2, 10), (1, 1)],
46            vec![(3, 2)],
47            vec![(1, 1), (3, 3), (4, 1)],
48            vec![(0, 7), (4, 2)],
49            vec![],
50        ];
51        let ans = spfa(&graph, 0);
52
53        assert_eq!(ans.unwrap(), vec![0, 1, 10, 3, 5]);
54    }
55    #[test]
56    fn test_2() {
57        let mx = 1_000_000_000_i64;
58
59        let k = 500_000;
60        let n = 3 * k + 1;
61        let mut h = vec![0; n];
62
63        for i in 0..k {
64            h[1 + i] = -(1 + i as i64);
65            h[1 + k + i] = mx - 2 * i as i64;
66            h[1 + 2 * k + 1] = -mx;
67        }
68
69        let mut g = vec![(0, 1)];
70
71        for i in 1..k {
72            g.push((i, i + 1));
73
74            g.push((i, i + k));
75
76            g.push((i + k, 2 * k + 1));
77        }
78        println!("{}", g.len());
79
80        //     let mut g = vec![vec![]];
81        //     g[0].push(1);
82        //     g[1].push(0);
83
84        //     for i in 1..k {
85        //         g[i].push(i + 1);
86        //         g[i + 1].push(i);
87
88        //         g[i].push(i + k);
89        //         g[i + k].push(i);
90
91        //         g[i + k].push(2 * k + 1);
92        //         g[2 * k + 1].push(i + k);
93        //     }
94
95        let mut e = vec![vec![]; n];
96        for (u, v) in g {
97            let (c1, c2) = if h[u] < h[v] {
98                (-(h[v] - h[u]), 2 * (h[v] - h[u]))
99            } else {
100                (2 * (h[u] - h[v]), -(h[u] - h[v]))
101            };
102            e[u].push((v, c2));
103            e[v].push((u, c1));
104        }
105
106        let ans = spfa(&e, 0).unwrap();
107
108        println!("{}", -ans.iter().min().unwrap());
109    }
110}
competitive_library/graph/shortest_path_faster_algorithm.rs

competitive_library/graph/
shortest_path_faster_algorithm.rs
