結果

問題 No.2712 Play more!
コンテスト
ユーザー nomeaning
提出日時 2024-03-31 14:35:54
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 79 ms / 2,000 ms
コード長 2,576 bytes
コンパイル時間 12,354 ms
コンパイル使用メモリ 401,540 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-09-30 23:47:14
合計ジャッジ時間 12,984 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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