結果
問題 | No.2695 Warp Zone |
ユーザー |
|
提出日時 | 2024-03-23 07:58:56 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 3,045 bytes |
コンパイル時間 | 20,681 ms |
コンパイル使用メモリ | 377,112 KB |
実行使用メモリ | 33,664 KB |
最終ジャッジ日時 | 2024-09-30 13:07:09 |
合計ジャッジ時間 | 20,494 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
fn main() {input!{h: usize, w: usize, n: usize,abcd: [(usize, usize, usize, usize); n],}// 頂点情報// (WarpのS,G * n S, G)let sz = 2 + n*2;let mut p = vec![(0, 0); sz];for i in 0..n {p[2*i] = (abcd[i].0, abcd[i].1);p[2*i+1] = (abcd[i].2, abcd[i].3);}p[sz-2] = (1, 1);p[sz-1] = (h, w);// costの隣接行列を用意const INF: usize = 1 << 60;let mut cost_t = vec![vec![INF; sz]; sz];for i in 0..sz {for j in 0..sz {let cost = p[i].0.abs_diff(p[j].0) + p[i].1.abs_diff(p[j].1);cost_t[i][j] = min(cost_t[i][j], cost);}}for i in 0..n {cost_t[2*i][2*i+1] = min(cost_t[2*i][2*i+1], 1);}// s -> gへのダイクストラ// hp = 最短距離、頂点let mut hp = BinaryHeap::new();hp.push(Reverse((0, sz-2)));let mut used = vec![false; sz];let mut dist = vec![INF; sz];while hp.len() > 0 {let (cdist, cp) = hp.pop().unwrap().0;if used[cp] { continue; }used[cp] = true;for j in 0..sz {let cost = cost_t[cp][j];if cdist + cost < dist[j] {dist[j] = cdist + cost;hp.push(Reverse((dist[j], j)));}}}println!("{}", dist[sz-1]);}// ---------- begin input macro ----------#[macro_export]macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}#[macro_export]macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}#[macro_export]macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, bytes) => {read_value!($iter, String).bytes().collect::<Vec<u8>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}// ---------- end input macro ----------#[allow(unused)]use std::{io::stderr, io::stdin, io::BufRead, io::Write,mem::swap,cmp::min, cmp::max,cmp::Reverse,collections::HashSet, collections::BTreeSet,collections::HashMap, collections::BTreeMap,collections::BinaryHeap,collections::VecDeque,};