結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2020-07-01 19:25:27 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,422 bytes |
コンパイル時間 | 12,594 ms |
コンパイル使用メモリ | 387,848 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-08 05:29:06 |
合計ジャッジ時間 | 13,003 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 4 |
other | WA * 40 |
ソースコード
use std::{ collections::VecDeque, io::{self, Read as _}, }; fn main() { let mut input = "".to_owned(); io::stdin().read_to_string(&mut input).unwrap(); let mut input = input.split_ascii_whitespace(); macro_rules! read( ([$ty:tt; $len:expr]) => ((0..$len).map(|_| read!($ty)).collect::<Vec<_>>()); (Usize1) => (read!(usize) - 1); ($ty:tt) => (input.next().unwrap().parse::<$ty>().unwrap()); ); let n = read!(usize); let c = read!(usize); let v = read!(usize); let ss = read!([Usize1; v]); let ts = read!([Usize1; v]); let ys = read!([usize; v]); let ms = read!([u32; v]); let graph = { let mut graph = vec![vec![]; n]; for (((s, t), y), m) in ss.into_iter().zip(ts).zip(ys).zip(ms) { graph[s].push((t, y, m)); } graph }; let mut cost = vec![vec![u32::max_value(); n]; c + 1]; cost[c][0] = 0; let mut queue = VecDeque::from(vec![(c, 0)]); while let Some((c, s)) = queue.pop_front() { for &(t, y, m) in &graph[s] { if y <= c && cost[c][s] + m < cost[c - y][t] { cost[c - y][t] = cost[c][s] + m; queue.push_back((c - y, t)); } } } let ans = (0..=c).map(|c| cost[c][0]).min().unwrap(); if ans == u32::max_value() { println!("-1"); } else { println!("{}", ans); } }