library_checker/graph/
shortest_path.rs

1#[doc(no_inline)]
2pub use competitive::graph::{DirectedGraphScanner, DirectedSparseGraph, ShortestPathExt};
3use competitive::prelude::*;
4
5#[verify::library_checker("shortest_path")]
6pub fn shortest_path(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, m, s, t, (g, c): @DirectedGraphScanner::<usize, u64>::new(n, m));
10    let sp = g.standard_sp_additive().with_parent().dijkstra([s], &c);
11    if let Some(path) = sp.path_to(&g, t) {
12        iter_print!(writer, sp.dist[t], path.len() - 1; @it2d path.windows(2));
13    } else {
14        iter_print!(writer, -1);
15    }
16}