Skip to main content

ShortestPathExt

competitive::graph::shortest_path

Trait ShortestPathExt 

Source 
pub trait ShortestPathExt: Graph {
    // Provided methods
    fn standard_sp<'a, M>(
        &'a self,
    ) -> ShortestPathBuilder<'a, Self, StandardSp<M>>
       where Self: Sized,
             M: Monoid<T: Bounded + Ord> { ... }
    fn standard_sp_additive<'a, T>(
        &'a self,
    ) -> ShortestPathBuilder<'a, Self, StandardSp<AdditiveOperation<T>>>
       where Self: Sized,
             T: Clone + Zero + Add<Output = T> + Bounded + Ord { ... }
    fn option_sp<'a, M>(&'a self) -> ShortestPathBuilder<'a, Self, OptionSp<M>>
       where Self: Sized,
             M: Monoid<T: Ord> { ... }
    fn option_sp_additive<'a, T>(
        &'a self,
    ) -> ShortestPathBuilder<'a, Self, OptionSp<AdditiveOperation<T>>>
       where Self: Sized,
             T: Clone + Zero + Add<Output = T> + Ord { ... }
    fn path_folding_sp<'a, M, S>(
        &'a self,
    ) -> ShortestPathBuilder<'a, Self, PathFoldingSp<M, S>>
       where Self: Sized,
             M: Monoid<T: Bounded + Ord>,
             S: SemiRing { ... }
    fn path_folding_sp_additive_addmul<'a, T, U>(
        &'a self,
    ) -> ShortestPathBuilder<'a, Self, PathFoldingSp<AdditiveOperation<T>, AddMulOperation<U>>>
       where Self: Sized,
             T: Clone + Zero + Add<Output = T> + Bounded + Ord,
             U: DotProduct + One { ... }
}

Provided Methods§

Source

fn standard_sp<'a, M>(&'a self) -> ShortestPathBuilder<'a, Self, StandardSp<M>>
where Self: Sized, M: Monoid<T: Bounded + Ord>,

Source

fn standard_sp_additive<'a, T>( &'a self, ) -> ShortestPathBuilder<'a, Self, StandardSp<AdditiveOperation<T>>>
where Self: Sized, T: Clone + Zero + Add<Output = T> + Bounded + Ord,

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_1_a.rs (line 11)
8pub fn grl_1_a(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
11    let cost = graph.standard_sp_additive().dijkstra([r], |eid| d[eid]);
12    for u in graph.vertices() {
13        if cost[u].is_maximum() {
14            pp!("INF");
15        } else {
16            pp!(cost[u]);
17        }
18    }
19}
More examples
Hide additional examples
crates/library_checker/src/graph/shortest_path.rs (line 9)
5pub fn shortest_path(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, s, t, (g, c): @DirectedGraphScanner::<usize, u64>::new(n, m));
8    let sp = g
9        .standard_sp_additive()
10        .with_parent()
11        .dijkstra_to([s], t, |eid| c[eid]);
12    if let Some(path) = sp.path_to(&g, t) {
13        pp!(sp.dist[t], path.len() - 1; @it2d path.windows(2));
14    } else {
15        pp!(-1);
16    }
17}
Source

fn option_sp<'a, M>(&'a self) -> ShortestPathBuilder<'a, Self, OptionSp<M>>
where Self: Sized, M: Monoid<T: Ord>,

Source

fn option_sp_additive<'a, T>( &'a self, ) -> ShortestPathBuilder<'a, Self, OptionSp<AdditiveOperation<T>>>
where Self: Sized, T: Clone + Zero + Add<Output = T> + Ord,

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_1_a.rs (line 25)
22pub fn grl_1_a_option(reader: impl Read, writer: impl Write) {
23    prepare_io!(reader, writer);
24    sc!(vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
25    let cost = graph.option_sp_additive().dijkstra([r], |eid| Some(d[eid]));
26    for u in graph.vertices() {
27        match cost[u] {
28            Some(d) => pp!(d),
29            None => pp!("INF"),
30        };
31    }
32}
More examples
Hide additional examples
crates/aizu_online_judge/src/grl/grl_1_b.rs (line 9)
5pub fn grl_1_b(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(vs, es, r, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
8    let cost = graph
9        .option_sp_additive()
10        .bellman_ford([r], |eid| Some(d[eid]), true);
11    if let Some(cost) = cost {
12        for u in graph.vertices() {
13            match cost[u] {
14                Some(d) => pp!(d),
15                None => pp!("INF"),
16            };
17        }
18    } else {
19        pp!("NEGATIVE CYCLE");
20    }
21}
crates/aizu_online_judge/src/grl/grl_1_c.rs (line 12)
8pub fn grl_1_c(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(vs, es, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
11    let cost = graph
12        .option_sp_additive()
13        .warshall_floyd_ap(|eid| Some(Saturating(d[eid])));
14    if graph.vertices().any(|u| cost[u][u].unwrap().0 < 0) {
15        pp!("NEGATIVE CYCLE");
16    } else {
17        for u in graph.vertices() {
18            for v in graph.vertices() {
19                match cost[u][v] {
20                    Some(d) => pp!(d.0, !),
21                    None => pp!("INF", !),
22                };
23                pp!(if v + 1 == vs { '\n' } else { ' ' }, !);
24            }
25        }
26    }
27}
Source

fn path_folding_sp<'a, M, S>( &'a self, ) -> ShortestPathBuilder<'a, Self, PathFoldingSp<M, S>>
where Self: Sized, M: Monoid<T: Bounded + Ord>, S: SemiRing,

Source

fn path_folding_sp_additive_addmul<'a, T, U>( &'a self, ) -> ShortestPathBuilder<'a, Self, PathFoldingSp<AdditiveOperation<T>, AddMulOperation<U>>>
where Self: Sized, T: Clone + Zero + Add<Output = T> + Bounded + Ord, U: DotProduct + One,

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors§

Source§

impl<G> ShortestPathExt for G
where G: Graph + ?Sized,