Trait ShortestPathExt 

pub trait ShortestPathExt: GraphBase {
    // Provided methods
    fn standard_sp<'a, M>(
        &'a self,
    ) -> ShortestPathBuilder<'a, Self, StandardSp<M>>
       where Self: Sized + GraphBase,
             M: Monoid<T: Bounded + Ord> { ... }
    fn standard_sp_additive<'a, T>(
        &'a self,
    ) -> ShortestPathBuilder<'a, Self, StandardSp<AdditiveOperation<T>>>
       where Self: Sized + GraphBase,
             T: Clone + Zero + Add<Output = T> + Bounded + Ord { ... }
    fn option_sp<'a, M>(&'a self) -> ShortestPathBuilder<'a, Self, OptionSp<M>>
       where Self: Sized + GraphBase,
             M: Monoid<T: Ord> { ... }
    fn option_sp_additive<'a, T>(
        &'a self,
    ) -> ShortestPathBuilder<'a, Self, OptionSp<AdditiveOperation<T>>>
       where Self: Sized + GraphBase,
             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 + GraphBase,
             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 + GraphBase,
             T: Clone + Zero + Add<Output = T> + Bounded + Ord,
             U: Clone + Zero + One + Add<Output = U> + Mul<Output = U> { ... }
}

Provided Methods

fn standard_sp<'a, M>(&'a self) -> ShortestPathBuilder<'a, Self, StandardSp<M>>

where Self: Sized + GraphBase, M: Monoid<T: Bounded + Ord>,

fn standard_sp_additive<'a, T>( &'a self, ) -> ShortestPathBuilder<'a, Self, StandardSp<AdditiveOperation<T>>>

where Self: Sized + GraphBase, T: Clone + Zero + Add<Output = T> + Bounded + Ord,

Examples found in repository

crates/library_checker/src/graph/shortest_path.rs (line 10)

pub fn shortest_path(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, m, s, t, (g, c): @DirectedGraphScanner::<usize, u64>::new(n, m));
    let sp = g.standard_sp_additive().with_parent().dijkstra([s], &c);
    if let Some(path) = sp.path_to(&g, t) {
        iter_print!(writer, sp.dist[t], path.len() - 1; @it2d path.windows(2));
    } else {
        iter_print!(writer, -1);
    }
}

crates/aizu_online_judge/src/grl/grl_1_a.rs (line 13)

pub fn grl_1_a(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
    let cost = graph.standard_sp_additive().dijkstra([r], &d);
    for u in graph.vertices() {
        if cost[u].is_maximum() {
            writeln!(writer, "INF").ok();
        } else {
            writeln!(writer, "{}", cost[u]).ok();
        }
    }
}

fn option_sp<'a, M>(&'a self) -> ShortestPathBuilder<'a, Self, OptionSp<M>>

where Self: Sized + GraphBase, M: Monoid<T: Ord>,

fn option_sp_additive<'a, T>( &'a self, ) -> ShortestPathBuilder<'a, Self, OptionSp<AdditiveOperation<T>>>

where Self: Sized + GraphBase, T: Clone + Zero + Add<Output = T> + Ord,

Examples found in repository

crates/aizu_online_judge/src/grl/grl_1_a.rs (line 29)

pub fn grl_1_a_option(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
    let cost = graph
        .option_sp_additive()
        .dijkstra([r], &|eid| Some(d[eid]));
    for u in graph.vertices() {
        match cost[u] {
            Some(d) => writeln!(writer, "{}", d).ok(),
            None => writeln!(writer, "INF").ok(),
        };
    }
}

crates/aizu_online_judge/src/grl/grl_1_b.rs (line 11)

pub fn grl_1_b(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, vs, es, r, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
    let cost = graph
        .option_sp_additive()
        .bellman_ford([r], &|eid| Some(d[eid]), true);
    if let Some(cost) = cost {
        for u in graph.vertices() {
            match cost[u] {
                Some(d) => writeln!(writer, "{}", d).ok(),
                None => writeln!(writer, "INF").ok(),
            };
        }
    } else {
        writeln!(writer, "NEGATIVE CYCLE").ok();
    }
}

crates/aizu_online_judge/src/grl/grl_1_c.rs (line 14)

pub fn grl_1_c(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, vs, es, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
    let cost = graph
        .option_sp_additive()
        .warshall_floyd_ap(&|eid| Some(Saturating(d[eid])));
    if graph.vertices().any(|u| cost[u][u].unwrap().0 < 0) {
        writeln!(writer, "NEGATIVE CYCLE").ok();
    } else {
        for u in graph.vertices() {
            for v in graph.vertices() {
                match cost[u][v] {
                    Some(d) => write!(writer, "{}", d.0),
                    None => write!(writer, "INF"),
                }
                .ok();
                write!(writer, "{}", if v + 1 == vs { '\n' } else { ' ' }).ok();
            }
        }
    }
}

fn path_folding_sp<'a, M, S>( &'a self, ) -> ShortestPathBuilder<'a, Self, PathFoldingSp<M, S>>

where Self: Sized + GraphBase, 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 + GraphBase, T: Clone + Zero + Add<Output = T> + Bounded + Ord, U: Clone + Zero + One + Add<Output = U> + Mul<Output = U>,

Implementors

impl<G> ShortestPathExt for G

where G: GraphBase,