結果
問題 | No.1283 Extra Fee |
ユーザー | fukafukatani |
提出日時 | 2020-11-06 22:08:17 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 371 ms / 2,000 ms |
コード長 | 3,556 bytes |
コンパイル時間 | 1,498 ms |
コンパイル使用メモリ | 161,308 KB |
実行使用メモリ | 85,072 KB |
最終ジャッジ日時 | 2023-08-10 05:59:56 |
合計ジャッジ時間 | 7,798 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,384 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,384 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,384 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,384 KB |
testcase_08 | AC | 1 ms
4,384 KB |
testcase_09 | AC | 1 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 14 ms
6,108 KB |
testcase_12 | AC | 17 ms
6,796 KB |
testcase_13 | AC | 12 ms
5,208 KB |
testcase_14 | AC | 51 ms
15,828 KB |
testcase_15 | AC | 91 ms
24,908 KB |
testcase_16 | AC | 18 ms
6,864 KB |
testcase_17 | AC | 288 ms
69,480 KB |
testcase_18 | AC | 323 ms
73,388 KB |
testcase_19 | AC | 344 ms
82,684 KB |
testcase_20 | AC | 314 ms
72,120 KB |
testcase_21 | AC | 339 ms
79,596 KB |
testcase_22 | AC | 279 ms
66,316 KB |
testcase_23 | AC | 330 ms
85,056 KB |
testcase_24 | AC | 347 ms
85,032 KB |
testcase_25 | AC | 366 ms
85,056 KB |
testcase_26 | AC | 371 ms
85,052 KB |
testcase_27 | AC | 359 ms
85,072 KB |
testcase_28 | AC | 366 ms
85,052 KB |
testcase_29 | AC | 312 ms
76,056 KB |
コンパイルメッセージ
warning: unused variable: `i` --> Main.rs:26:9 | 26 | for i in 0..m { | ^ help: if this is intentional, prefix it with an underscore: `_i` | = note: `#[warn(unused_variables)]` on by default warning: 1 warning emitted
ソースコード
#![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 get_idx(i: usize, x: usize, y: usize, w: usize) -> usize { i + x * 2 + y * 2 * w } fn main() { let v = read_vec::<usize>(); let (n, m) = (v[0], v[1]); let mut cost_dict = HashMap::new(); for i in 0..m { let v = read_vec::<i64>(); let (h, w, c) = (v[0] as usize - 1, v[1] as usize - 1, v[2]); cost_dict.insert((h, w), c); } let mut edges = vec![vec![]; n * n * 2]; for y in 0..n { for x in 0..n { let cost; let cur0 = get_idx(0, x, y, n); let cur1 = get_idx(1, x, y, n); if cost_dict.contains_key(&(y, x)) { cost = cost_dict[&(y, x)]; } else { cost = 0; } for (adj_x, adj_y) in get_adjacents(x, y, n, n) { let adj0 = get_idx(0, adj_x, adj_y, n); let adj1 = get_idx(1, adj_x, adj_y, n); edges[adj0].push(Edge { to: cur0, cost: cost + 1, }); edges[adj1].push(Edge { to: cur1, cost: cost + 1, }); edges[adj0].push(Edge { to: cur1, cost: 1 }); } } } let d = solve(&edges, 0); let ans = d[get_idx(1, n - 1, n - 1, n)]; println!("{}", ans); } fn get_adjacents(x: usize, y: usize, w: usize, h: usize) -> Vec<(usize, usize)> { let mut adjacents = vec![]; if x > 0 { adjacents.push((x - 1, y)); } if y > 0 { adjacents.push((x, y - 1)); } if y < h - 1 { adjacents.push((x, y + 1)); } if x < w - 1 { adjacents.push((x + 1, y)); } adjacents } 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() } use std::cmp::Ordering; use std::collections::BinaryHeap; const INF: i64 = 100000_00000_00000; #[derive(PartialEq, Debug)] struct MinInt { value: i64, } impl Eq for MinInt {} impl PartialOrd for MinInt { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { other.value.partial_cmp(&self.value) } } impl Ord for MinInt { fn cmp(&self, other: &MinInt) -> Ordering { other.value.cmp(&self.value) } } fn make_pair(x: i64, y: usize) -> (MinInt, usize) { (MinInt { value: x }, y) } #[derive(Debug, Clone)] struct Edge { to: usize, cost: i64, } fn solve(edges: &Vec<Vec<Edge>>, start_idx: usize) -> Vec<i64> { let num_apexes = edges.len(); let mut d = vec![INF; num_apexes]; d[start_idx] = 0; let mut que = BinaryHeap::new(); que.push(make_pair(0, start_idx)); while let Some((u, v)) = que.pop() { if d[v] < u.value { continue; } for e in &edges[v] { if d[v] != INF && d[e.to] > d[v] + e.cost { d[e.to] = d[v] + e.cost; que.push(make_pair(d[e.to], e.to)); } } } d }