Submission #35334583

Source Code Expand

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

macro_rules! chmin {
    ($a: expr, $b: expr) => {
        $a = $a.min($b);
    };
}

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

    let inf = std::u64::MAX / 2;

    // let mut dp = vec![vec![inf; n]; k + 1];
    // dp[0][0] = 0;
    // for i in 0..k {
    //     let (a, b, c) = edges[seq[i]];
    //     for v in 0..n {
    //         dp[i + 1][v] = dp[i][v];
    //         if v == a {
    //             chmin!(dp[i + 1][b], dp[i][a] + c);
    //         }
    //     }
    // }

    let mut dp = vec![inf; n];
    dp[0] = 0;
    for i in 0..k {
        let (a, b, c) = edges[seq[i]];
        chmin!(dp[b], dp[a] + c);
    }

    // let ans = dp[k][n - 1];
    let ans = dp[n - 1];
    if ans == inf {
        println!("-1");
    } else {
        println!("{}", ans);
    }
}

Submission Info

Submission Time
Task E - Subsequence Path
User ikd
Language Rust (1.42.0)
Score 500
Code Size 946 Byte
Status AC
Exec Time 43 ms
Memory 15776 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 29
Set Name Test Cases
Sample example_00.txt, example_01.txt, example_02.txt
All example_00.txt, example_01.txt, example_02.txt, test_00.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
Case Name Status Exec Time Memory
example_00.txt AC 4 ms 2004 KiB
example_01.txt AC 6 ms 2000 KiB
example_02.txt AC 2 ms 2096 KiB
test_00.txt AC 39 ms 15776 KiB
test_01.txt AC 2 ms 2036 KiB
test_02.txt AC 34 ms 10024 KiB
test_03.txt AC 20 ms 7932 KiB
test_04.txt AC 15 ms 4488 KiB
test_05.txt AC 26 ms 6440 KiB
test_06.txt AC 34 ms 11528 KiB
test_07.txt AC 40 ms 12396 KiB
test_08.txt AC 34 ms 10444 KiB
test_09.txt AC 43 ms 14040 KiB
test_10.txt AC 43 ms 13776 KiB
test_11.txt AC 27 ms 9296 KiB
test_12.txt AC 22 ms 6924 KiB
test_13.txt AC 19 ms 5076 KiB
test_14.txt AC 39 ms 12352 KiB
test_15.txt AC 10 ms 5184 KiB
test_16.txt AC 17 ms 5308 KiB
test_17.txt AC 21 ms 7560 KiB
test_18.txt AC 41 ms 13452 KiB
test_19.txt AC 20 ms 7224 KiB
test_20.txt AC 29 ms 9636 KiB
test_21.txt AC 39 ms 12576 KiB
test_22.txt AC 38 ms 11520 KiB
test_23.txt AC 41 ms 15244 KiB
test_24.txt AC 42 ms 15080 KiB
test_25.txt AC 41 ms 15320 KiB