結果
問題 | No.1638 Robot Maze |
ユーザー |
![]() |
提出日時 | 2021-08-06 22:32:26 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 28 ms / 2,000 ms |
コード長 | 2,788 bytes |
コンパイル時間 | 14,080 ms |
コンパイル使用メモリ | 395,916 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-17 02:36:21 |
合計ジャッジ時間 | 17,044 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#![allow(unused_imports)] use std::cmp::*; use std::collections::*; use std::io::Write; use std::ops::Bound::*; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let v = read_vec::<usize>(); let (h, w) = (v[0], v[1]); let v = read_vec::<i64>(); let (u, d, r, l, k, p) = (v[0], v[1], v[2], v[3], v[4], v[5]); let v = read_vec::<usize>(); let (xs, ys, xt, yt) = (v[0] - 1, v[1] - 1, v[2] - 1, v[3] - 1); let mut grid = vec![vec![]; h]; for i in 0..h { grid[i] = read::<String>().chars().collect::<Vec<_>>(); } let to_index = |x, y| x + y * w; let mut edges = vec![vec![]; w * h]; for y in 0..h { for x in 0..w { if grid[y][x] == '#' { continue; } let cost = if grid[y][x] == '@' { p } else { 0 }; let cur = to_index(x, y); if x > 0 { let adj = to_index(x - 1, y); edges[cur].push((adj, l + cost)); } if y > 0 { let adj = to_index(x, y - 1); edges[cur].push((adj, u + cost)); } if x < w - 1 { let adj = to_index(x + 1, y); edges[cur].push((adj, r + cost)); } if y < h - 1 { let adj = to_index(x, y + 1); edges[cur].push((adj, d + cost)); } } } let s = to_index(ys, xs); let t = to_index(yt, xt); let d = solve(&edges, s); debug!(s, t, d); if d[t] <= k { println!("Yes"); } else { println!("No"); } } fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } type Cost = i64; const INF: Cost = 100000_00000_00000; fn solve(edges: &Vec<Vec<(usize, Cost)>>, start_idx: usize) -> Vec<Cost> { let num_apexes = edges.len(); let mut d = vec![INF; num_apexes]; d[start_idx] = 0; let mut que = std::collections::BinaryHeap::new(); que.push((std::cmp::Reverse(0), start_idx)); while let Some((u, v)) = que.pop() { if d[v] < u.0 { continue; } for e in &edges[v] { if d[v] != INF && d[e.0] > d[v] + e.1 { d[e.0] = d[v] + e.1; que.push((std::cmp::Reverse(d[e.0]), e.0)); } } } d }