提出 #16581872


ソースコード 拡げる

Copy
use proconio::input;
use proconio::marker::Usize1;

fn dijkstra(n: usize, inf: u64, e: &Vec<Vec<(usize, u64)>>, s: usize) -> Vec<u64> {
    let mut d = vec![inf; n];
    let mut pq = std::collections::BinaryHeap::new();
    d[s] = 0;
    pq.push(std::cmp::Reverse((0, s)));
    while let Some(std::cmp::Reverse((w_u, u))) = pq.pop() {
        if w_u > d[u] {
            continue;
        }
        for &(v, w_v) in e[u].iter() {
            let w = w_u + w_v;
            if w < d[v] {
                d[v] = w;
                pq.push(std::cmp::Reverse((w, v)));
            }
        }
    }
    d
}

fn adjacency_list(n: usize, uvw: &Vec<(usize, usize, u64)>) -> Vec<Vec<(usize, u64)>> {
    let mut e = vec![vec![]; n];
    for &(u, v, w) in uvw.iter() {
        e[u].push((v, w));
        e[v].push((u, w));
    }
    e
}

fn main() {
    input! {
        n: usize,
        m: usize,
        abt: [(Usize1, Usize1, u64); m],
    };

    let e = adjacency_list(n, &abt);

    let inf = 1_000_000_000_000_u64;
    let mut ans = inf;
    for i in 0..n {
        let d = dijkstra(n, inf, &e, i);
        ans = std::cmp::min(ans, d.into_iter().max().unwrap());
    }
    println!("{}", ans);
}

提出情報

提出日時
問題 D - バスと避けられない運命
ユーザ bouzuya
言語 Rust (1.42.0)
得点 100
コード長 1195 Byte
結果 AC
実行時間 86 ms
メモリ 6412 KB

ジャッジ結果

セット名 All
得点 / 配点 100 / 100
結果
AC × 39
セット名 テストケース
All sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt
ケース名 結果 実行時間 メモリ
sample_01.txt AC 7 ms 2120 KB
sample_02.txt AC 1 ms 2136 KB
sample_03.txt AC 2 ms 2116 KB
test_01.txt AC 1 ms 2092 KB
test_02.txt AC 10 ms 2044 KB
test_03.txt AC 86 ms 6412 KB
test_04.txt AC 22 ms 2344 KB
test_05.txt AC 45 ms 3712 KB
test_06.txt AC 9 ms 2392 KB
test_07.txt AC 68 ms 5696 KB
test_08.txt AC 2 ms 2072 KB
test_09.txt AC 38 ms 3448 KB
test_10.txt AC 7 ms 2364 KB
test_11.txt AC 16 ms 2456 KB
test_12.txt AC 31 ms 2600 KB
test_13.txt AC 13 ms 2328 KB
test_14.txt AC 18 ms 2556 KB
test_15.txt AC 74 ms 5720 KB
test_16.txt AC 17 ms 2516 KB
test_17.txt AC 36 ms 3424 KB
test_18.txt AC 29 ms 2556 KB
test_19.txt AC 19 ms 2544 KB
test_20.txt AC 16 ms 2548 KB
test_21.txt AC 2 ms 2088 KB
test_22.txt AC 26 ms 2536 KB
test_23.txt AC 2 ms 2116 KB
test_24.txt AC 5 ms 2000 KB
test_25.txt AC 7 ms 2080 KB
test_26.txt AC 2 ms 2140 KB
test_27.txt AC 3 ms 2104 KB
test_28.txt AC 7 ms 2116 KB
test_29.txt AC 5 ms 2116 KB
test_30.txt AC 2 ms 2108 KB
test_31.txt AC 2 ms 2060 KB
test_32.txt AC 5 ms 2120 KB
test_33.txt AC 7 ms 2192 KB
test_34.txt AC 2 ms 1964 KB
test_35.txt AC 3 ms 2108 KB
test_36.txt AC 7 ms 2016 KB