competitive_programming_rs/graph/
shortest_path.rs

1pub mod bellman_ford {
2    pub fn shortest_path(
3        graph: &[Vec<(usize, i64)>],
4        start: usize,
5        inf: i64,
6    ) -> (Vec<i64>, Vec<bool>) {
7        let n = graph.len();
8        let mut dist = vec![inf; n];
9        dist[start] = 0;
10        for _ in 0..n {
11            for v in 0..n {
12                for &(to, cost) in &graph[v] {
13                    if dist[v] == inf || dist[to] <= dist[v] + cost {
14                        continue;
15                    }
16                    dist[to] = dist[v] + cost;
17                }
18            }
19        }
20
21        let mut negative = vec![false; n];
22        for _ in 0..n {
23            for v in 0..n {
24                for &(to, cost) in &graph[v] {
25                    if dist[v] == inf {
26                        continue;
27                    }
28                    if dist[to] > dist[v] + cost {
29                        dist[to] = dist[v] + cost;
30                        negative[to] = true;
31                    }
32                    if negative[v] {
33                        negative[to] = true;
34                    }
35                }
36            }
37        }
38
39        (dist, negative)
40    }
41}
42
43#[cfg(test)]
44mod tests {
45    use super::*;
46    use crate::utils::test_helper::Tester;
47    const INF: i64 = 1 << 60;
48
49    #[test]
50    fn solve_grl_1_b() {
51        let tester = Tester::new("./assets/GRL_1_B/in/", "./assets/GRL_1_B/out/");
52        tester.test_solution(|sc| {
53            let v: usize = sc.read();
54            let e: usize = sc.read();
55            let r: usize = sc.read();
56
57            let mut graph = vec![vec![]; v];
58
59            for _ in 0..e {
60                let s: usize = sc.read();
61                let t: usize = sc.read();
62                let d: i64 = sc.read();
63                graph[s].push((t, d));
64            }
65
66            let (dist, negative) = bellman_ford::shortest_path(&graph, r, INF);
67            let mut neg = false;
68            for &b in &negative {
69                neg = neg || b;
70            }
71
72            if neg {
73                sc.write("NEGATIVE CYCLE\n");
74            } else {
75                for i in 0..v {
76                    if dist[i] == INF {
77                        sc.write("INF\n");
78                    } else {
79                        sc.write(format!("{}\n", dist[i]));
80                    }
81                }
82            }
83        });
84    }
85}
competitive_programming_rs/graph/shortest_path.rs

competitive_programming_rs/graph/
shortest_path.rs
