Skip to main content

aizu_online_judge/grl/
grl_1_b.rs

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