aizu_online_judge/grl/
grl_1_c.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::AdditiveOperation,
5    graph::{DirectedGraphScanner, OptionSp, ShortestPathExt},
6    num::Saturating,
7};
8
9#[verify::aizu_online_judge("GRL_1_C")]
10pub fn grl_1_c(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, vs, es, (graph, d): @DirectedGraphScanner::<usize, i64>::new(vs, es));
14    let cost = graph
15        .warshall_floyd_ap::<OptionSp<AdditiveOperation<_>>, _>(&|eid| Some(Saturating(d[eid])));
16    if graph.vertices().any(|u| cost[u][u].unwrap().0 < 0) {
17        writeln!(writer, "NEGATIVE CYCLE").ok();
18    } else {
19        for u in graph.vertices() {
20            for v in graph.vertices() {
21                match cost[u][v] {
22                    Some(d) => write!(writer, "{}", d.0),
23                    None => write!(writer, "INF"),
24                }
25                .ok();
26                write!(writer, "{}", if v + 1 == vs { '\n' } else { ' ' }).ok();
27            }
28        }
29    }
30}
aizu_online_judge/grl/grl_1_c.rs

aizu_online_judge/grl/
grl_1_c.rs
