結果

問題 No.788 トラックの移動
ユーザー titiatitia
提出日時 2024-05-15 03:46:41
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 368 ms / 2,000 ms
コード長 2,181 bytes
コンパイル時間 13,110 ms
コンパイル使用メモリ 396,520 KB
実行使用メモリ 33,536 KB
最終ジャッジ日時 2024-12-20 10:09:06
合計ジャッジ時間 16,023 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 368 ms
33,408 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 86 ms
9,856 KB
testcase_05 AC 351 ms
33,408 KB
testcase_06 AC 363 ms
33,408 KB
testcase_07 AC 1 ms
6,816 KB
testcase_08 AC 1 ms
6,816 KB
testcase_09 AC 1 ms
6,820 KB
testcase_10 AC 1 ms
6,816 KB
testcase_11 AC 1 ms
6,816 KB
testcase_12 AC 1 ms
6,820 KB
testcase_13 AC 1 ms
6,820 KB
testcase_14 AC 1 ms
6,816 KB
testcase_15 AC 113 ms
33,536 KB
testcase_16 AC 317 ms
33,536 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable `N` should have a snake case name
  --> src/main.rs:12:9
   |
12 |     let N: usize = first_line_split.next().unwrap().parse().unwrap();
   |         ^ help: convert the identifier to snake case: `n`
   |
   = note: `#[warn(non_snake_case)]` on by default

warning: variable `M` should have a snake case name
  --> src/main.rs:13:9
   |
13 |     let M: usize = first_line_split.next().unwrap().parse().unwrap();
   |         ^ help: convert the identifier to snake case: `m`

warning: variable `L` should have a snake case name
  --> src/main.rs:14:13
   |
14 |     let mut L: usize = first_line_split.next().unwrap().parse().unwrap();
   |             ^ help: convert the identifier to snake case: `l`

warning: variable `T` should have a snake case name
  --> src/main.rs:18:9
   |
18 |     let T: Vec<i64> = second_line
   |         ^ help: convert the identifier to snake case: `t`

warning: variable `E` should have a snake case name
  --> src/main.rs:29:13
   |
29 |     let mut E = vec![vec![]; N];
   |             ^ help: convert the identifier to snake case: `e`

warning: variable `D` should have a snake case name
  --> src/main.rs:43:13
   |
43 |     let mut D = vec![vec![inf; N]; N];
   |             ^ help: convert the identifier to snake case: `d`

warning: variable `Q` should have a snake case name
  --> src/main.rs:47:17
   |
47 |         let mut Q = BinaryHeap::new();
   |                 ^ help: convert the identifier to snake case: `q`

warning: variable `ANS` should have a snake case name
  --> src/main.rs:64:13
   |
64 |     let mut ANS = 1 << 61;
   |             ^^^ help: convert the identifier to snake case: `ans`

ソースコード

diff # 

use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::io::{self, BufRead};

fn main() {
    let stdin = io::stdin();
    let mut input = stdin.lock().lines();

    // Read N, M, L
    let first_line = input.next().unwrap().unwrap();
    let mut first_line_split = first_line.split_whitespace();
    let N: usize = first_line_split.next().unwrap().parse().unwrap();
    let M: usize = first_line_split.next().unwrap().parse().unwrap();
    let mut L: usize = first_line_split.next().unwrap().parse().unwrap();

    // Read T
    let second_line = input.next().unwrap().unwrap();
    let T: Vec<i64> = second_line
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();

    if T.iter().filter(|&&x| x == 0).count() >= N - 1 {
        println!("0");
        return;
    }

    L -= 1;
    let mut E = vec![vec![]; N];

    for _ in 0..M {
        let line = input.next().unwrap().unwrap();
        let mut parts = line.split_whitespace();
        let a: usize = parts.next().unwrap().parse().unwrap();
        let b: usize = parts.next().unwrap().parse().unwrap();
        let c: i64 = parts.next().unwrap().parse().unwrap();

        E[a - 1].push((b - 1, c));
        E[b - 1].push((a - 1, c));
    }

    let inf: i64 = 1 << 60;
    let mut D = vec![vec![inf; N]; N];

    for i in 0..N {
        D[i][i] = 0;
        let mut Q = BinaryHeap::new();
        Q.push((Reverse(0), i));

        while let Some((Reverse(dis), ind)) = Q.pop() {
            if D[i][ind] != dis {
                continue;
            }

            for &(to, length) in &E[ind] {
                if D[i][to] > dis + length {
                    D[i][to] = dis + length;
                    Q.push((Reverse(D[i][to]), to));
                }
            }
        }
    }

    let mut ANS = 1 << 61;

    for i in 0..N {
        let mut score: i64 = 0;
        for j in 0..N {
            score += T[j] * D[i][j] * 2;
        }

        for j in 0..N {
            if T[j] > 0 {
                score += D[L][j] - D[i][j];
                ANS = ANS.min(score);
                score -= D[L][j] - D[i][j];
            }
        }
    }

    println!("{}", ANS);
}
0