結果

問題 No.1473 おでぶなおばけさん
ユーザー maimai
提出日時 2021-04-22 02:02:39
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 2,470 bytes
コンパイル時間 840 ms
コンパイル使用メモリ 151,060 KB
実行使用メモリ 13,060 KB
最終ジャッジ日時 2023-09-17 09:48:55
合計ジャッジ時間 6,289 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 125 ms
13,056 KB
testcase_08 WA -
testcase_09 AC 125 ms
13,060 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 34 ms
4,956 KB
testcase_14 AC 24 ms
4,380 KB
testcase_15 AC 46 ms
6,612 KB
testcase_16 AC 52 ms
5,652 KB
testcase_17 AC 4 ms
4,376 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 AC 44 ms
5,236 KB
testcase_42 AC 44 ms
5,264 KB
testcase_43 AC 68 ms
10,596 KB
testcase_44 AC 68 ms
10,596 KB
testcase_45 AC 68 ms
10,620 KB
testcase_46 AC 72 ms
8,412 KB
testcase_47 AC 88 ms
9,688 KB
testcase_48 AC 83 ms
9,588 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::{collections::*, io::Read};

fn take_token<R: std::io::BufRead>(cin: &mut R) -> String {
    cin.bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>()
}
#[allow(unused)]
macro_rules! scan {
    ($io:expr => $t:ty) => (take_token(&mut $io).parse::<$t>().unwrap());
    ($io:expr => $t:tt * $n:expr) => ((0..$n).map(|_| scan!($io => $t)).collect::<Vec<_>>());
    ($io:expr => $($t:tt),*) => (($(scan!($io => $t)),*));
    ($io:expr => $($t:tt),* * $n:expr) => ((0..$n).map(|_| ($(scan!($io => $t)),*)).collect::<Vec<_>>());
}

struct Graph<T: Clone = ()>(Vec<Vec<(usize, T)>>);

impl<T: Clone> Graph<T> {
    fn to<'a>(&self, i: usize) -> &Vec<(usize, T)> {
        &(self.0)[i]
    }
}

struct GraphBuilder<T: Clone = ()>(Graph<T>);

impl<T: Clone> GraphBuilder<T> {
    fn new(n: usize) -> Self {
        Self(Graph::<T>(vec![Vec::<(usize, T)>::new(); n]))
    }
    fn connect(&mut self, u: usize, v: usize, item: T) {
        (self.0 .0)[u].push((v, item.clone()));
        (self.0 .0)[v].push((u, item));
    }
    fn build(self) -> Graph<T> {
        self.0
    }
}

fn main() {
    solve(std::io::stdin().lock())
}

fn solve<R: std::io::BufRead>(mut cin: R) {
    let (n, m) = scan!(cin => i32, i32);
    let mut builder = GraphBuilder::<i32>::new(n as usize);
    for _ in 0..m {
        let (u, v, m) = scan!(cin => i32, i32, i32);
        builder.connect((u - 1) as usize, (v - 1) as usize, m);
    }
    let graph = builder.build();
    let mut visited = vec![(0, 0); n as usize];
    let mut que = BinaryHeap::<(i32, i32, usize)>::new();
    que.push((i32::max_value(), 0, 0));
    visited[0] = (i32::max_value(), 0);
    while let Some((w, d, v)) = que.pop() {
        // let d = visited[v].1;
        // if v as i32 == n - 1 {
        //     println!("{} {}", w, d);
        //     return;
        // }
        if visited[v].0 > w {
            continue;
        }
        for (v2, cap) in graph.to(v).iter() {
            let w2 = w.min(*cap);
            // println!(" {} >={} : ({}->{})", visited[*v2].0, w2, v, *v2);
            if visited[*v2].0 >= w2 {
                continue;
            }
            visited[*v2] = (w2, d + 1);
            que.push((w2, d + 1, *v2));
        }
    }
    println!(
        "{} {}",
        visited[(n - 1) as usize].0,
        visited[(n - 1) as usize].1
    );
    // panic!("non-connective");
}
0