結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2024-07-31 15:59:51 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,420 bytes |
コンパイル時間 | 13,486 ms |
コンパイル使用メモリ | 388,168 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-31 16:00:06 |
合計ジャッジ時間 | 14,972 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
use std::collections::BTreeSet; fn main() { proconio::input! { n: u64, c: u64, v: u64, s: [u64; v], t: [u64; v], y: [u64; v], m: [u64; v], } let goal = n - 1; let s = s.into_iter().map(|s| s - 1).collect::<Vec<_>>(); let t = t.into_iter().map(|t| t - 1).collect::<Vec<_>>(); let mut stym = s .into_iter() .zip(t.into_iter()) .zip(y.into_iter()) .zip(m.into_iter()) .map(|(((s, t), y), m)| (s, t, y, m)) .collect::<Vec<_>>(); stym.sort_unstable(); let mut moves = BTreeSet::new(); moves.insert((0, 0, 0)); let mut mtime_min = u64::MAX; loop { let mut new_moves = BTreeSet::new(); moves.into_iter().for_each(|(town, cost, mtime)| { stym.iter() .filter(|(s, _, y, _)| *s == town && cost + y <= c) .for_each(|(_, t, y, m)| { if *t == goal { mtime_min = std::cmp::min(mtime_min, m + mtime); } else if mtime + m <= mtime_min { new_moves.insert((*t, cost + y, mtime + m)); } }); }); moves = new_moves; if moves.is_empty() { break; } } if mtime_min == u64::MAX { println!("-1"); } else { println!("{mtime_min}"); } }