結果
問題 | No.2739 Time is money |
ユーザー | naut |
提出日時 | 2024-04-24 00:20:06 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 157 ms / 2,000 ms |
コード長 | 3,366 bytes |
コンパイル時間 | 1,449 ms |
コンパイル使用メモリ | 168,832 KB |
実行使用メモリ | 35,456 KB |
最終ジャッジ日時 | 2024-04-24 00:20:11 |
合計ジャッジ時間 | 5,124 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 0 ms
5,248 KB |
testcase_01 | AC | 0 ms
5,376 KB |
testcase_02 | AC | 54 ms
19,200 KB |
testcase_03 | AC | 115 ms
26,752 KB |
testcase_04 | AC | 46 ms
18,688 KB |
testcase_05 | AC | 67 ms
19,456 KB |
testcase_06 | AC | 86 ms
23,680 KB |
testcase_07 | AC | 157 ms
35,456 KB |
testcase_08 | AC | 155 ms
35,072 KB |
testcase_09 | AC | 155 ms
34,688 KB |
testcase_10 | AC | 87 ms
31,104 KB |
testcase_11 | AC | 151 ms
34,688 KB |
testcase_12 | AC | 119 ms
34,944 KB |
testcase_13 | AC | 102 ms
34,816 KB |
testcase_14 | AC | 98 ms
34,816 KB |
testcase_15 | AC | 69 ms
27,904 KB |
testcase_16 | AC | 67 ms
27,776 KB |
testcase_17 | AC | 150 ms
33,920 KB |
testcase_18 | AC | 152 ms
33,920 KB |
testcase_19 | AC | 78 ms
27,904 KB |
ソースコード
#![allow(non_snake_case, unused_imports, unused_must_use)] use std::io::{self, prelude::*}; use std::str; fn main() { let (stdin, stdout) = (io::stdin(), io::stdout()); let mut scan = Scanner::new(stdin.lock()); let mut out = io::BufWriter::new(stdout.lock()); macro_rules! input { ($T: ty) => { scan.token::<$T>() }; ($T: ty, $N: expr) => { (0..$N).map(|_| scan.token::<$T>()).collect::<Vec<_>>() }; } let N = input!(usize); let M = input!(usize); let X = input!(usize); let mut edges = vec![]; for _ in 0..M { let u = input!(usize); let v = input!(usize); let c = input!(usize); let t = input!(usize); edges.push((u - 1, v - 1, c + t * X)); edges.push((v - 1, u - 1, c + t * X)); } let dist = dijkstras_algorithm(N, &edges, 0)[N - 1]; match dist { Some(d) => { writeln!(out, "{}", (d + X - 1) / X); } None => { writeln!(out, "-1"); } } } pub fn dijkstras_algorithm< W: Sized + std::ops::Add<Output = W> + PartialOrd + Ord + Default + Clone + Copy, >( size: usize, directed_edges: &[(usize, usize, W)], start: usize, ) -> Vec<Option<W>> { assert!(start < size); let graph = { let mut g = vec![vec![]; size]; for &(from, to, weight) in directed_edges.iter() { assert!(from < size && to < size); g[from].push((to, weight)); } g }; let mut dist = vec![None; size]; dist[start] = Some(W::default()); let mut seen = vec![false; size]; let mut hq = std::collections::BinaryHeap::new(); hq.push((std::cmp::Reverse(W::default()), start)); while let Some((_, now)) = hq.pop() { if seen[now] { continue; } seen[now] = true; for &(nxt, weight) in graph[now].iter() { match dist[nxt] { Some(prev_dist) => { if dist[now].unwrap() + weight < prev_dist { let d = dist[now].unwrap() + weight; dist[nxt] = Some(d); hq.push((std::cmp::Reverse(d), nxt)); } } None => { let d = dist[now].unwrap() + weight; dist[nxt] = Some(d); hq.push((std::cmp::Reverse(d), nxt)); } } } } dist } struct Scanner<R> { reader: R, buf_str: Vec<u8>, buf_iter: str::SplitWhitespace<'static>, } impl<R: BufRead> Scanner<R> { fn new(reader: R) -> Self { Self { reader, buf_str: vec![], buf_iter: "".split_whitespace(), } } fn token<T: str::FromStr>(&mut self) -> T { loop { if let Some(token) = self.buf_iter.next() { return token.parse().ok().expect("Failed parse"); } self.buf_str.clear(); self.reader .read_until(b'\n', &mut self.buf_str) .expect("Failed read"); self.buf_iter = unsafe { let slice = str::from_utf8_unchecked(&self.buf_str); std::mem::transmute(slice.split_whitespace()) } } } }