結果
問題 | No.2712 Play more! |
ユーザー |
|
提出日時 | 2024-06-20 22:08:01 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 1,335 bytes |
コンパイル時間 | 14,326 ms |
コンパイル使用メモリ | 404,876 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-20 22:08:18 |
合計ジャッジ時間 | 16,379 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
use proconio::{input, marker::Usize1}; fn main() { input! { n:usize, m:usize, a:[i64;n], abc:[(Usize1,Usize1,i64);m], } let mut g = vec![vec![]; n]; let mut rg = vec![vec![]; n]; for &(u, v, w) in abc.iter() { g[u].push((v, w - a[u])); rg[v].push(u); } let mut vis = vec![false; n]; f(n - 1, &mut vis, &rg); const INF: i64 = std::i64::MAX; let mut dists = vec![INF; n]; dists[0] = 0; for i in 1..=n { for j in 0..n { for &(k, w) in g[j].iter() { if !vis[j] || !vis[k] { continue; } if dists[j] != INF && dists[k] > dists[j] + w { dists[k] = dists[j] + w; if i == n { println!("inf"); return; } } } } } let ans = -abc .iter() .filter(|&&(_, v, _)| v == n - 1) .map(|&(u, v, w)| dists[u] + w - a[u] - a[v]) .min() .unwrap(); println!("{}", ans); } fn f(crr: usize, vis: &mut Vec<bool>, g: &Vec<Vec<usize>>) { vis[crr] = true; for &nxt in g[crr].iter() { if vis[nxt] { continue; } f(nxt, vis, g); } }