Skip to main content

aizu_online_judge/grl/
grl_1_c.rs

1use competitive::prelude::*;
2use competitive::{
3    graph::{DirectedGraphScanner, ShortestPathExt},
4    num::Saturating,
5};
6
7#[verify::aizu_online_judge("GRL_1_C")]
8pub fn grl_1_c(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(vs, es, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
11    let cost = graph
12        .option_sp_additive()
13        .warshall_floyd_ap(|eid| Some(Saturating(d[eid])));
14    if graph.vertices().any(|u| cost[u][u].unwrap().0 < 0) {
15        pp!("NEGATIVE CYCLE");
16    } else {
17        for u in graph.vertices() {
18            for v in graph.vertices() {
19                match cost[u][v] {
20                    Some(d) => pp!(d.0, !),
21                    None => pp!("INF", !),
22                };
23                pp!(if v + 1 == vs { '\n' } else { ' ' }, !);
24            }
25        }
26    }
27}