結果
問題 | No.2739 Time is money |
ユーザー |
![]() |
提出日時 | 2024-04-21 11:08:52 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 153 ms / 2,000 ms |
コード長 | 892 bytes |
コンパイル時間 | 11,923 ms |
コンパイル使用メモリ | 384,528 KB |
実行使用メモリ | 33,688 KB |
最終ジャッジ日時 | 2024-10-13 09:50:10 |
合計ジャッジ時間 | 16,767 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#![allow(non_snake_case)] use std::collections::BinaryHeap; use proconio::{input}; fn main() { input!{ n: usize, m: usize, x: u64, es: [(usize, usize, u64, u64); m] } let mut adj = vec![Vec::new(); n]; for (u, v, c, t) in es { adj[u - 1].push((v - 1, c + t * x)); adj[v - 1].push((u - 1, c + t * x)); } let mut dist = vec![u64::MAX; n]; dist[0] = 0; let mut pq = BinaryHeap::new(); pq.push((0, 0)); while let Some((d, u)) = pq.pop() { if (-d) as u64 > dist[u] { continue; } for (v, c) in &adj[u] { let d1 = (-d) as u64 + c; if d1 < dist[*v] { dist[*v] = d1; pq.push((-(d1 as i64), *v)); } } } if dist[n - 1] == u64::MAX { println!("-1"); } else { println!("{}", (dist[n - 1] + x - 1) / x); } }