Submission #677106
Source Code Expand
use std::io; use std::str::FromStr; use std::cmp::{ min, max }; use std::collections::{ BinaryHeap, VecDeque }; const INF: i64 = 1_000_000_007; type Edge = (usize, i64); fn dij(adj: &Vec<Vec<Edge>>, s:usize) -> Vec<i64> { let mut dist = vec![INF; adj.len()]; dist[s] = 0; let mut heap = BinaryHeap::new(); heap.push((0, s)); while let Some((_, v)) = heap.pop() { for edge in &adj[v] { let (u, cost) = *edge; if dist[u] > dist[v] + cost { dist[u] = dist[v] + cost; heap.push(( -dist[u] , u )); } } } dist } fn main() { let mut sc = Scanner::new(); let n: usize = sc.cin(); let m: usize = sc.cin(); let t: i64 = sc.cin(); let mut a = vec![0; n]; for i in 0..n { a[i] = sc.cin(); }; let mut neigh = vec![vec![]; n]; let mut reigh = vec![vec![]; n]; for _ in 0..m { let x = sc.cin::<usize>() - 1; let y = sc.cin::<usize>() - 1; let c: i64 = sc.cin(); neigh[x].push((y, c)); reigh[y].push((x, c)); } let dist = dij(&neigh, 0); let rist = dij(&reigh, 0); let mut ans = a[0] * t; for i in 1..n { if dist[i] == INF || rist[i] == INF { continue } let rest = t - dist[i] as i64 - rist[i] as i64 ; if rest > 0 { ans = max(ans, rest * a[i]) } } println!("{}", ans); } #[allow(dead_code)] struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } } fn reserve(&mut self) { while self.buffer.len() == 0 { let mut line = String::new(); let _ = self.stdin.read_line(&mut line); for w in line.split_whitespace() { self.buffer.push_back(String::from(w)); } } } fn cin<T: FromStr>(&mut self) -> T { self.reserve(); match self.buffer.pop_front().unwrap().parse::<T>() { Ok(a) => a, Err(_) => panic!("parse err") } } fn get_char(&mut self) -> char { self.reserve(); let head = self.buffer[0].chars().nth(0).unwrap(); let tail = String::from( &self.buffer[0][1..] ); if tail.len()>0 { self.buffer[0]=tail } else { self.buffer.remove(0); } head } }
Submission Info
Submission Time | |
---|---|
Task | D - トレジャーハント |
User | cympfh |
Language | Rust (1.15.1) |
Score | 100 |
Code Size | 2416 Byte |
Status | AC |
Exec Time | 167 ms |
Memory | 23416 KB |
Compile Error
./Main.rs:3:17: 3:20 warning: unused import, #[warn(unused_imports)] on by default ./Main.rs:3 use std::cmp::{ min, max }; ^~~
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 50 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 10_rand_09.txt, 10_rand_10.txt, 10_rand_12.txt, 10_rand_13.txt, 30_max_01.txt, 30_max_02.txt, 30_max_03.txt, 30_max_04.txt, 30_max_05.txt, 30_max_06.txt, 40_corner_01.txt, 40_corner_02.txt, 40_corner_03.txt, 40_corner_04.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 4 ms | 380 KB |
00_example_02.txt | AC | 4 ms | 380 KB |
00_example_03.txt | AC | 4 ms | 380 KB |
10_rand_01.txt | AC | 12 ms | 2300 KB |
10_rand_02.txt | AC | 38 ms | 4220 KB |
10_rand_03.txt | AC | 16 ms | 3068 KB |
10_rand_04.txt | AC | 8 ms | 1532 KB |
10_rand_05.txt | AC | 18 ms | 3836 KB |
10_rand_06.txt | AC | 20 ms | 4988 KB |
10_rand_07.txt | AC | 28 ms | 6780 KB |
10_rand_08.txt | AC | 13 ms | 2940 KB |
10_rand_09.txt | AC | 25 ms | 6268 KB |
10_rand_10.txt | AC | 8 ms | 1788 KB |
10_rand_12.txt | AC | 63 ms | 4220 KB |
10_rand_13.txt | AC | 58 ms | 4220 KB |
30_max_01.txt | AC | 134 ms | 8316 KB |
30_max_02.txt | AC | 163 ms | 10620 KB |
30_max_03.txt | AC | 113 ms | 7420 KB |
30_max_04.txt | AC | 160 ms | 18680 KB |
30_max_05.txt | AC | 163 ms | 18680 KB |
30_max_06.txt | AC | 163 ms | 18680 KB |
40_corner_01.txt | AC | 153 ms | 23416 KB |
40_corner_02.txt | AC | 159 ms | 23416 KB |
40_corner_03.txt | AC | 161 ms | 23288 KB |
40_corner_04.txt | AC | 167 ms | 23416 KB |
50_small_01.txt | AC | 5 ms | 508 KB |
50_small_02.txt | AC | 4 ms | 380 KB |
50_small_03.txt | AC | 4 ms | 380 KB |
50_small_04.txt | AC | 5 ms | 380 KB |
50_small_05.txt | AC | 6 ms | 636 KB |
50_small_06.txt | AC | 6 ms | 636 KB |
50_small_07.txt | AC | 4 ms | 380 KB |
50_small_08.txt | AC | 4 ms | 380 KB |
50_small_09.txt | AC | 4 ms | 508 KB |
50_small_10.txt | AC | 4 ms | 380 KB |
60_hand_01.txt | AC | 4 ms | 380 KB |
60_hand_02.txt | AC | 4 ms | 380 KB |
60_hand_03.txt | AC | 4 ms | 380 KB |
60_hand_04.txt | AC | 6 ms | 380 KB |
70_max_01.txt | AC | 35 ms | 2172 KB |
70_max_02.txt | AC | 34 ms | 2172 KB |
70_max_03.txt | AC | 34 ms | 2172 KB |