結果
問題 | No.1283 Extra Fee |
ユーザー | cotton_fn_ |
提出日時 | 2020-11-07 13:10:57 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 91 ms / 2,000 ms |
コード長 | 7,599 bytes |
コンパイル時間 | 13,817 ms |
コンパイル使用メモリ | 379,000 KB |
実行使用メモリ | 9,856 KB |
最終ジャッジ日時 | 2024-11-16 07:06:05 |
合計ジャッジ時間 | 15,039 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,820 KB |
testcase_02 | AC | 1 ms
6,820 KB |
testcase_03 | AC | 1 ms
6,816 KB |
testcase_04 | AC | 1 ms
6,820 KB |
testcase_05 | AC | 1 ms
6,820 KB |
testcase_06 | AC | 1 ms
6,816 KB |
testcase_07 | AC | 1 ms
6,816 KB |
testcase_08 | AC | 1 ms
6,816 KB |
testcase_09 | AC | 1 ms
6,816 KB |
testcase_10 | AC | 1 ms
6,820 KB |
testcase_11 | AC | 5 ms
6,816 KB |
testcase_12 | AC | 6 ms
6,820 KB |
testcase_13 | AC | 4 ms
6,820 KB |
testcase_14 | AC | 14 ms
6,820 KB |
testcase_15 | AC | 20 ms
6,816 KB |
testcase_16 | AC | 5 ms
6,820 KB |
testcase_17 | AC | 87 ms
9,600 KB |
testcase_18 | AC | 72 ms
6,912 KB |
testcase_19 | AC | 74 ms
6,912 KB |
testcase_20 | AC | 71 ms
6,824 KB |
testcase_21 | AC | 67 ms
6,816 KB |
testcase_22 | AC | 63 ms
6,820 KB |
testcase_23 | AC | 55 ms
7,168 KB |
testcase_24 | AC | 56 ms
7,168 KB |
testcase_25 | AC | 75 ms
7,168 KB |
testcase_26 | AC | 80 ms
7,296 KB |
testcase_27 | AC | 81 ms
7,040 KB |
testcase_28 | AC | 79 ms
7,168 KB |
testcase_29 | AC | 91 ms
9,856 KB |
ソースコード
#![allow(unused_imports, unused_macros)]use kyoproio::*;use std::{collections::*,io::{self, prelude::*},iter,mem::{replace, swap},};fn run<I: Input, O: Write>(mut kin: I, mut out: O) {macro_rules! output { ($($args:expr),+) => { write!(&mut out, $($args),+).unwrap(); }; }macro_rules! outputln {($($args:expr),+) => { output!($($args),+); outputln!(); };() => { output!("\n"); if cfg!(debug_assertions) { out.flush().unwrap(); } }}let (n, m): (usize, usize) = kin.input();let mut fee = vec![vec![0; n]; n];for (h, w, c) in kin.iter::<(usize, usize, i32)>().take(m) {fee[h - 1][w - 1] = c;}let mut dist = vec![vec![[i64::max_value(); 2]; n]; n];dist[0][0][0] = 0;let mut que = BinaryHeap::new();que.push(Ordered(0, (0, 0, 0)));while let Some(Ordered(d, (i, j, f))) = que.pop() {let d = -d;if d > dist[i][j][f] {continue;}for &(di, dj) in &[(1, 0), (0, 1), (-1, 0), (0, -1)] {let ti = (i as isize + di) as usize;let tj = (j as isize + dj) as usize;if ti < n && tj < n {// let h = (2 * n - 2 - ti - tj) as i64;let td = d + 1 + fee[ti][tj] as i64;if td < dist[ti][tj][f] {que.push(Ordered(-td, (ti, tj, f)));dist[ti][tj][f] = td;}if f == 0 {let td = d + 1;if td < dist[ti][tj][1] {que.push(Ordered(-td, (ti, tj, 1)));dist[ti][tj][1] = td;}}}}}outputln!("{}", dist[n - 1][n - 1][1]);}use std::cmp::Ordering;#[derive(Clone, Copy, Debug)]pub struct Ordered<T, U>(pub T, pub U);impl<T: Ord, U> PartialEq for Ordered<T, U> {fn eq(&self, other: &Self) -> bool {self.0.eq(&other.0)}}impl<T: Ord, U> Eq for Ordered<T, U> {}impl<T: Ord, U> PartialOrd for Ordered<T, U> {fn partial_cmp(&self, other: &Self) -> Option<Ordering> {self.0.partial_cmp(&other.0)}}impl<T: Ord, U> Ord for Ordered<T, U> {fn cmp(&self, other: &Self) -> Ordering {self.0.cmp(&other.0)}}// -----------------------------------------------------------------------------fn main() -> io::Result<()> {std::thread::Builder::new().stack_size(64 * 1024 * 1024).spawn(|| {run(KInput::new(io::stdin().lock()),io::BufWriter::new(io::stdout().lock()),)})?.join().unwrap();Ok(())}// -----------------------------------------------------------------------------pub mod kyoproio {use std::io::prelude::*;pub trait Input {fn bytes(&mut self) -> &[u8];fn str(&mut self) -> &str {std::str::from_utf8(self.bytes()).unwrap()}fn input<T: InputParse>(&mut self) -> T {T::input(self)}fn iter<T: InputParse>(&mut self) -> Iter<T, Self> {Iter(self, std::marker::PhantomData)}fn seq<T: InputParse, B: std::iter::FromIterator<T>>(&mut self, n: usize) -> B {self.iter().take(n).collect()}}pub struct KInput<R> {src: R,buf: Vec<u8>,pos: usize,len: usize,}impl<R: Read> KInput<R> {pub fn new(src: R) -> Self {Self {src,buf: vec![0; 1 << 16],pos: 0,len: 0,}}}impl<R: Read> Input for KInput<R> {fn bytes(&mut self) -> &[u8] {loop {while let Some(delim) = self.buf[self.pos..self.len].iter().position(|b| b.is_ascii_whitespace()){let range = self.pos..self.pos + delim;self.pos += delim + 1;if delim > 0 {return &self.buf[range];}}if self.pos > 0 {self.buf.copy_within(self.pos..self.len, 0);self.len -= self.pos;self.pos = 0;}if self.len >= self.buf.len() {self.buf.resize(2 * self.buf.len(), 0);}let read = self.src.read(&mut self.buf[self.len..]).unwrap();if read == 0 {let range = self.pos..self.len;self.pos = self.len;return &self.buf[range];}self.len += read;}}}pub struct Iter<'a, T, I: ?Sized>(&'a mut I, std::marker::PhantomData<*const T>);impl<'a, T: InputParse, I: Input + ?Sized> Iterator for Iter<'a, T, I> {type Item = T;fn next(&mut self) -> Option<T> {Some(self.0.input())}}pub trait InputParse: Sized {fn input<I: Input + ?Sized>(src: &mut I) -> Self;}impl InputParse for Vec<u8> {fn input<I: Input + ?Sized>(src: &mut I) -> Self {src.bytes().to_owned()}}macro_rules! from_str_impl {{ $($T:ty)* } => {$(impl InputParse for $T {fn input<I: Input + ?Sized>(src: &mut I) -> Self {src.str().parse::<$T>().unwrap()}})*}}from_str_impl! { String char bool f32 f64 }macro_rules! parse_int_impl {{ $($I:ty: $U:ty)* } => {$(impl InputParse for $I {fn input<I: Input + ?Sized>(src: &mut I) -> Self {let f = |s: &[u8]| s.iter().fold(0, |x, b| 10 * x + (b & 0xf) as $I);let s = src.bytes();if let Some((&b'-', t)) = s.split_first() { -f(t) } else { f(s) }}}impl InputParse for $U {fn input<I: Input + ?Sized>(src: &mut I) -> Self {src.bytes().iter().fold(0, |x, b| 10 * x + (b & 0xf) as $U)}})*};}parse_int_impl! { isize:usize i8:u8 i16:u16 i32:u32 i64:u64 i128:u128 }macro_rules! tuple_impl {($H:ident $($T:ident)*) => {impl<$H: InputParse, $($T: InputParse),*> InputParse for ($H, $($T),*) {fn input<I: Input + ?Sized>(src: &mut I) -> Self {($H::input(src), $($T::input(src)),*)}}tuple_impl!($($T)*);};() => {}}tuple_impl!(A B C D E F G);macro_rules! array_impl {{ $($N:literal)* } => {$(impl<T: InputParse> InputParse for [T; $N] {fn input<I: Input + ?Sized>(src: &mut I) -> Self {let mut arr = std::mem::MaybeUninit::uninit();unsafe {let ptr = arr.as_mut_ptr() as *mut T;for i in 0..$N {ptr.add(i).write(src.input());}arr.assume_init()}}})*};}array_impl! { 1 2 3 4 5 6 7 8 }#[macro_export]macro_rules! kdbg {($($v:expr),*) => {if cfg!(debug_assertions) { dbg!($($v),*) } else { ($($v),*) }}}}