bfs01/
lib.rs

1use std::collections::VecDeque;
2
3pub struct Cert<V>(Vec<Option<V>>);
4pub struct NoCert;
5
6pub struct Bfs01Sssp<V, I, C> {
7    cost: Vec<usize>,
8    prev: C,
9    index: I,
10    src: V,
11}
12
13impl<V, I> Bfs01Sssp<V, I, Cert<V>>
14where
15    V: Eq + Clone,
16    I: Fn(&V) -> usize,
17{
18    pub fn new_cert<D, J>(src: V, len: usize, index: I, delta: D) -> Self
19    where
20        D: Fn(&V) -> J,
21        J: Iterator<Item = (V, usize)>,
22    {
23        let mut cost = vec![len; len];
24        let mut prev = vec![None; len];
25        let mut deque = VecDeque::new();
26        cost[index(&src)] = 0;
27        deque.push_front((0, src.clone()));
28        while let Some((w, v)) = deque.pop_front() {
29            for (nv, dw) in delta(&v) {
30                let nw = w + dw;
31                let ni = index(&nv);
32                if cost[ni] > nw {
33                    cost[ni] = nw;
34                    prev[ni] = Some(v.clone());
35                    if dw == 0 {
36                        deque.push_front((nw, nv));
37                    } else {
38                        deque.push_back((nw, nv));
39                    }
40                }
41            }
42        }
43
44        Self { src, cost, prev: Cert(prev), index }
45    }
46    pub fn path(&self, dst: &V) -> Option<std::vec::IntoIter<V>> {
47        let mut i = (self.index)(dst);
48        if self.prev.0[i].is_none() {
49            return (&self.src == dst).then(|| vec![dst.clone()].into_iter());
50        }
51
52        let mut res = vec![dst.clone()];
53        while let Some(v) = &self.prev.0[i] {
54            i = (self.index)(v);
55            res.push(v.clone());
56        }
57        res.reverse();
58        Some(res.into_iter())
59    }
60}
61
62impl<V, I> Bfs01Sssp<V, I, NoCert>
63where
64    V: Eq + Clone,
65    I: Fn(&V) -> usize,
66{
67    pub fn new<D, J>(src: V, len: usize, index: I, delta: D) -> Self
68    where
69        D: Fn(&V) -> J,
70        J: Iterator<Item = (V, usize)>,
71    {
72        let mut cost = vec![len; len];
73        let mut deque = VecDeque::new();
74        cost[index(&src)] = 0;
75        deque.push_front((0, src.clone()));
76        while let Some((w, v)) = deque.pop_front() {
77            for (nv, dw) in delta(&v) {
78                let nw = w + dw;
79                let ni = index(&nv);
80                if cost[ni] > nw {
81                    cost[ni] = nw;
82                    if dw == 0 {
83                        deque.push_front((nw, nv));
84                    } else {
85                        deque.push_back((nw, nv));
86                    }
87                }
88            }
89        }
90
91        Self { src, cost, prev: NoCert, index }
92    }
93}
94
95impl<V, I, C> Bfs01Sssp<V, I, C>
96where
97    V: Eq + Clone,
98    I: Fn(&V) -> usize,
99{
100    pub fn cost(&self, dst: &V) -> Option<usize> {
101        let tmp = self.cost[(self.index)(dst)].clone();
102        (tmp < self.cost.len()).then_some(tmp)
103    }
104}
bfs01/lib.rs

bfs01/
lib.rs
