結果

問題 No.2712 Play more!
ユーザー nomeaningnomeaning
提出日時 2024-03-31 14:35:54
言語 Rust
(1.77.0)
結果
AC  
実行時間 123 ms / 2,000 ms
コード長 2,576 bytes
コンパイル時間 984 ms
コンパイル使用メモリ 185,032 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-04-03 12:09:54
合計ジャッジ時間 2,732 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,676 KB
testcase_01 AC 1 ms
6,676 KB
testcase_02 AC 1 ms
6,676 KB
testcase_03 AC 1 ms
6,676 KB
testcase_04 AC 1 ms
6,676 KB
testcase_05 AC 1 ms
6,676 KB
testcase_06 AC 1 ms
6,676 KB
testcase_07 AC 32 ms
6,676 KB
testcase_08 AC 32 ms
6,676 KB
testcase_09 AC 32 ms
6,676 KB
testcase_10 AC 1 ms
6,676 KB
testcase_11 AC 15 ms
6,676 KB
testcase_12 AC 85 ms
6,676 KB
testcase_13 AC 18 ms
6,676 KB
testcase_14 AC 56 ms
6,676 KB
testcase_15 AC 123 ms
6,676 KB
testcase_16 AC 8 ms
6,676 KB
testcase_17 AC 2 ms
6,676 KB
testcase_18 AC 7 ms
6,676 KB
testcase_19 AC 3 ms
6,676 KB
testcase_20 AC 29 ms
6,676 KB
testcase_21 AC 12 ms
6,676 KB
testcase_22 AC 52 ms
6,676 KB
testcase_23 AC 5 ms
6,676 KB
testcase_24 AC 8 ms
6,676 KB
testcase_25 AC 3 ms
6,676 KB
testcase_26 AC 10 ms
6,676 KB
testcase_27 AC 8 ms
6,676 KB
testcase_28 AC 3 ms
6,676 KB
testcase_29 AC 11 ms
6,676 KB
testcase_30 AC 89 ms
6,676 KB
testcase_31 AC 3 ms
6,676 KB
testcase_32 AC 3 ms
6,676 KB
testcase_33 AC 1 ms
6,676 KB
testcase_34 AC 1 ms
6,676 KB
testcase_35 AC 1 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::VecDeque;

fn main() {
    let stdin = std::io::stdin();
    let mut line = String::new();
    stdin.read_line(&mut line).unwrap();
    let line: Vec<&str> = line.split_whitespace().collect();
    let n = line[0].parse::<usize>().unwrap();
    let m = line[1].parse::<usize>().unwrap();

    let mut line = String::new();
    stdin.read_line(&mut line).unwrap();
    let a: Vec<_> = line
        .split_whitespace()
        .map(|s| s.parse::<i64>().unwrap())
        .collect();
    let mut g: Vec<Vec<(usize, i64)>> = vec![vec![]; n];
    // 逆グラフ
    let mut inv_g: Vec<Vec<usize>> = vec![vec![]; n];

    for _ in 0..m {
        let mut line = String::new();
        stdin.read_line(&mut line).unwrap();
        let line: Vec<_> = line.split_whitespace().collect();
        let l = line[0].parse::<usize>().unwrap();
        let r = line[1].parse::<usize>().unwrap();
        let d = line[2].parse::<i64>().unwrap();
        g[l - 1].push((r - 1, d));
        inv_g[r - 1].push(l - 1);
    }
    // 終点からの到達可能性
    let mut visited = vec![false; n];
    visited[n - 1] = true;
    let mut queue = VecDeque::new();
    queue.push_back(n - 1);
    while let Some(v) = queue.pop_front() {
        for &u in &inv_g[v] {
            if !visited[u] {
                visited[u] = true;
                queue.push_back(u);
            }
        }
    }
    assert!(visited[0]);
    // 始点からの最短コスト
    let mut min_cost = vec![None; n];
    min_cost[0] = Some(-a[0]);
    for loop_count in 0..(n + 1) {
        let mut updated = false;
        for v in 0..n {
            let Some(current_min_cost) = min_cost[v] else {
                continue;
            };
            for &(u, d) in &g[v] {
                if !visited[u] {
                    // 終点に到達できない負閉路を除外する
                    continue;
                }
                let next_cost = current_min_cost + d - a[u];
                if let Some(min_cost_u) = min_cost[u] {
                    if min_cost_u > next_cost {
                        min_cost[u] = Some(next_cost);
                        updated = true;
                    }
                } else {
                    min_cost[u] = Some(next_cost);
                    updated = true;
                }
            }
        }
        if !updated {
            println!("{}", -min_cost[n - 1].unwrap());
            break;
        }
        if loop_count == n {
            // 負閉路
            println!("inf");
            return;
        }
    }
}
0