Skip to main content

library_checker/graph/
minimum_steiner_tree.rs

1use competitive::graph::{SteinerTreeExt, UndirectedGraphScanner};
2use competitive::prelude::*;
3
4#[verify::library_checker("minimum_steiner_tree")]
5pub fn minimum_steiner_tree(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, (graph, weights): @UndirectedGraphScanner::<usize, u64>::new(n, m));
8    sc!(k, terminals: [usize; k]);
9    let tree = graph
10        .steiner_tree()
11        .with_standard_sp_additive()
12        .with_parent()
13        .solve(terminals[1..].iter().copied(), |eid| weights[eid]);
14    let edges = tree.edges_from_source(terminals[0]).unwrap();
15    pp!(tree.minimum_from_source(terminals[0]), edges.len(); @it edges);
16}