結果
問題 | No.2099 [Cherry Alpha B] Time Machine |
ユーザー |
|
提出日時 | 2022-10-14 23:10:16 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,617 bytes |
コンパイル時間 | 13,330 ms |
コンパイル使用メモリ | 401,580 KB |
実行使用メモリ | 316,520 KB |
最終ジャッジ日時 | 2024-06-26 17:03:24 |
合計ジャッジ時間 | 41,013 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 68 WA * 4 |
ソースコード
use std::{collections::BinaryHeap, cmp::Reverse};const INF: u32 = (1u32 << 30) - 1;const OFFSET: usize = 20000001;fn main() {let mut t = String::new();std::io::stdin().read_line(&mut t).ok();let t: isize = t.trim().parse().unwrap();let mut xa = String::new();std::io::stdin().read_line(&mut xa).ok();let xa: Vec<usize> = xa.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();let x = xa[0] as u32;let a = xa[1];let mut yb = String::new();std::io::stdin().read_line(&mut yb).ok();let yb: Vec<usize> = yb.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();let y = yb[0] as u32;let b = yb[1];let t = (t + OFFSET as isize) as usize;let goal = t as usize;let mut checked = vec![INF; OFFSET*2+1];checked[OFFSET] = 0;let mut pque = BinaryHeap::new();pque.push((Reverse(0u32), OFFSET));while let Some((Reverse(cost), pos)) = pque.pop() {if checked[pos] < cost { continue; }if pos+1 < checked.len() && pos+1 <= goal && checked[pos+1] > cost + 1 {pque.push((Reverse(cost+1), pos+1));checked[pos+1] = cost+1;}if pos+a < checked.len() && pos+a <= goal+a+1 && checked[pos+a] > cost + x {pque.push((Reverse(cost+x), pos+a));checked[pos+a] = cost+x;}if pos >= b && pos-b >= goal-b-1 && checked[pos-b] > cost + y {pque.push((Reverse(cost+y), pos-b));checked[pos-b] = cost+y;}if checked[goal] < INF { break; }}println!("{}", checked[goal]);}