結果
問題 | No.788 トラックの移動 |
ユーザー | titia |
提出日時 | 2024-05-15 03:46:41 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 363 ms / 2,000 ms |
コード長 | 2,181 bytes |
コンパイル時間 | 14,906 ms |
コンパイル使用メモリ | 387,056 KB |
実行使用メモリ | 33,408 KB |
最終ジャッジ日時 | 2024-05-15 03:47:00 |
合計ジャッジ時間 | 18,147 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 359 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,944 KB |
testcase_04 | AC | 84 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,940 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 1 ms
6,944 KB |
testcase_10 | AC | 1 ms
6,944 KB |
testcase_11 | AC | 1 ms
6,944 KB |
testcase_12 | AC | 1 ms
6,940 KB |
testcase_13 | AC | 1 ms
6,944 KB |
testcase_14 | AC | 1 ms
6,940 KB |
testcase_15 | AC | 112 ms
33,408 KB |
testcase_16 | AC | 317 ms
33,408 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`
ソースコード
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); }