結果
問題 | No.1283 Extra Fee |
ユーザー | koba-e964 |
提出日時 | 2020-11-06 21:54:17 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 404 ms / 2,000 ms |
コード長 | 4,951 bytes |
コンパイル時間 | 1,734 ms |
コンパイル使用メモリ | 165,488 KB |
実行使用メモリ | 79,316 KB |
最終ジャッジ日時 | 2023-08-10 05:57:37 |
合計ジャッジ時間 | 8,156 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,384 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 1 ms
4,384 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 16 ms
5,156 KB |
testcase_12 | AC | 19 ms
5,792 KB |
testcase_13 | AC | 13 ms
4,380 KB |
testcase_14 | AC | 56 ms
14,784 KB |
testcase_15 | AC | 89 ms
22,988 KB |
testcase_16 | AC | 18 ms
5,536 KB |
testcase_17 | AC | 357 ms
70,576 KB |
testcase_18 | AC | 318 ms
72,988 KB |
testcase_19 | AC | 336 ms
76,660 KB |
testcase_20 | AC | 311 ms
71,852 KB |
testcase_21 | AC | 316 ms
73,168 KB |
testcase_22 | AC | 283 ms
65,664 KB |
testcase_23 | AC | 362 ms
79,288 KB |
testcase_24 | AC | 404 ms
79,180 KB |
testcase_25 | AC | 345 ms
79,172 KB |
testcase_26 | AC | 354 ms
79,284 KB |
testcase_27 | AC | 350 ms
79,244 KB |
testcase_28 | AC | 354 ms
79,316 KB |
testcase_29 | AC | 392 ms
77,252 KB |
ソースコード
#[allow(unused_imports)] use std::cmp::*; #[allow(unused_imports)] use std::collections::*; use std::io::{Write, BufWriter}; // https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, [graph1; $len:expr]) => {{ let mut g = vec![vec![]; $len]; let ab = read_value!($next, [(usize1, usize1)]); for (a, b) in ab { g[a].push(b); g[b].push(a); } g }}; ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::<Vec<char>>() }; ($next:expr, usize1) => (read_value!($next, usize) - 1); ($next:expr, [ $t:tt ]) => {{ let len = read_value!($next, usize); read_value!($next, [$t; len]) }}; ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error")); } #[allow(unused)] macro_rules! debug { ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap()); } #[allow(unused)] macro_rules! debugln { ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap()); } /* * Dijkstra's algorithm. * Verified by: AtCoder ABC164 (https://atcoder.jp/contests/abc164/submissions/12423853) */ struct Dijkstra { edges: Vec<Vec<(usize, i64)>>, // adjacent list representation } impl Dijkstra { fn new(n: usize) -> Self { Dijkstra { edges: vec![Vec::new(); n] } } fn add_edge(&mut self, from: usize, to: usize, cost: i64) { self.edges[from].push((to, cost)); } /* * This function returns a Vec consisting of the distances from vertex source. */ fn solve(&self, source: usize, inf: i64) -> Vec<i64> { let n = self.edges.len(); let mut d = vec![inf; n]; // que holds (-distance, vertex), so that que.pop() returns the nearest element. let mut que = std::collections::BinaryHeap::new(); que.push((0, source)); while let Some((cost, pos)) = que.pop() { let cost = -cost; if d[pos] <= cost { continue; } d[pos] = cost; for &(w, c) in &self.edges[pos] { let newcost = cost + c; if d[w] > newcost { d[w] = newcost + 1; que.push((-newcost, w)); } } } return d; } } fn solve() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts { ($($format:tt)*) => (let _ = write!(out,$($format)*);); } #[allow(unused)] macro_rules! putvec { ($v:expr) => { for i in 0..$v.len() { puts!("{}{}", $v[i], if i + 1 == $v.len() {"\n"} else {" "}); } } } input! { n: usize, m: usize, hwc: [(usize1, usize1, i64); m], } let mut dijk = Dijkstra::new(2 * n * n); let mut fee = vec![vec![0; n]; n]; for &(h, w, c) in &hwc { fee[h][w] = c; } for i in 0..2 * n { for j in 0..n - 1 { let v = i * n + j; dijk.add_edge(v, v + 1, fee[i % n][j + 1] + 1); dijk.add_edge(v + 1, v, fee[i % n][j] + 1); if i < n { dijk.add_edge(v, n * n + v + 1, 1); dijk.add_edge(v + 1, n * n + v, 1); } } } for i in 0..2 * n { if i % n == n - 1 { continue; } for j in 0..n { let v = i * n + j; dijk.add_edge(v, v + n, fee[i % n + 1][j] + 1); dijk.add_edge(v + n, v, fee[i % n][j] + 1); if i < n { dijk.add_edge(v, n * n + v + n, 1); dijk.add_edge(v + n, n * n + v, 1); } } } let sol = dijk.solve(0, 1 << 50); puts!("{}\n", min(sol[2 * n * n - 1], sol[n * n - 1])); } fn main() { // In order to avoid potential stack overflow, spawn a new thread. let stack_size = 104_857_600; // 100 MB let thd = std::thread::Builder::new().stack_size(stack_size); thd.spawn(|| solve()).unwrap().join().unwrap(); }