competitive_library/graph/
zero_one_bfs.rs

1//! ダイクストラ
2
3use std::collections::VecDeque;
4#[derive(Debug, Clone)]
5pub struct Node {
6    position: usize,
7    cost: i64,
8}
9impl Node {
10    #[inline]
11    pub fn new(position: usize, cost: i64) -> Self {
12        Node { position, cost }
13    }
14}
15
16pub fn bfs(edge: &[Vec<(usize, i64)>], start: usize, end: usize) -> Option<i64> {
17    assert_ne!(start, end);
18    let mut costs = vec![None; edge.len()];
19    let mut nodes = VecDeque::new();
20    nodes.push_back(Node::new(start, 0));
21
22    while let Some(Node { position, cost }) = nodes.pop_front() {
23        if costs[position].is_some() {
24            continue;
25        }
26        if position == end {
27            return Some(cost);
28        }
29        costs[position] = Some(cost);
30
31        edge[position]
32            .iter()
33            .filter(|(to, c)| costs[*to].filter(|&d| d <= cost + c).is_none())
34            .for_each(|&(to, c)| {
35                if c == 0 {
36                    nodes.push_front(Node::new(to, cost));
37                } else {
38                    nodes.push_back(Node::new(to, cost + 1));
39                }
40            });
41    }
42    None
43}
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48    #[test]
49    fn test_dijkstra() {
50        let graph = vec![
51            vec![(2, 1), (1, 0)],
52            vec![(3, 1)],
53            vec![(1, 1), (3, 0), (4, 1)],
54            vec![(0, 1), (4, 0)],
55            vec![],
56        ];
57
58        assert_eq!(bfs(&graph, 0, 1), Some(0));
59        assert_eq!(bfs(&graph, 0, 3), Some(1));
60        assert_eq!(bfs(&graph, 3, 0), Some(1));
61        assert_eq!(bfs(&graph, 0, 4), Some(1));
62        assert_eq!(bfs(&graph, 4, 0), None);
63    }
64    #[test]
65    #[should_panic]
66    fn test_panic() {
67        bfs(&[], 0, 0);
68    }
69}
competitive_library/graph/zero_one_bfs.rs

competitive_library/graph/
zero_one_bfs.rs
