Skip to main content

library_checker/graph/
shortest_path.rs

1use competitive::graph::{DirectedGraphScanner, ShortestPathExt};
2use competitive::prelude::*;
3
4#[verify::library_checker("shortest_path")]
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}