結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2022-12-10 02:13:21 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 486 ms / 4,000 ms |
コード長 | 1,623 bytes |
コンパイル時間 | 13,601 ms |
コンパイル使用メモリ | 378,144 KB |
実行使用メモリ | 25,088 KB |
最終ジャッジ日時 | 2024-10-14 23:27:43 |
合計ジャッジ時間 | 20,350 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
use std::{cmp::Reverse, collections::BinaryHeap}; const INF: usize = 1usize << 60; fn dijkstra(start: usize, paths: &Vec<Vec<(usize, usize)>>) -> Vec<Vec<usize>> { let n = paths.len(); let mut que = BinaryHeap::new(); que.push((Reverse(0), 0, start)); let mut costs = vec![vec![INF; 2]; n]; costs[start][0] = 0; costs[start][1] = 0; while let Some((Reverse(cost), used, u)) = que.pop() { if cost > costs[u][used] { continue; } for &(v, vcost) in paths[u].iter() { if costs[u][used] + vcost < costs[v][used] { costs[v][used] = costs[u][used] + vcost; que.push((Reverse(costs[v][used]), used, v)); } if used == 0 && costs[u][0] < costs[v][1] { costs[v][1] = costs[u][0]; que.push((Reverse(costs[v][1]), 1, v)); } } } costs } fn main() { let mut nm = String::new(); std::io::stdin().read_line(&mut nm).ok(); let nm: Vec<usize> = nm.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let n = nm[0]; let m = nm[1]; let mut paths = vec![vec![]; n]; for _ in 0..m { let mut abc = String::new(); std::io::stdin().read_line(&mut abc).ok(); let abc: Vec<usize> = abc.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let a = abc[0]-1; let b = abc[1]-1; let c = abc[2]; paths[a].push((b, c)); paths[b].push((a, c)); } let dists = dijkstra(0, &paths); for i in 0..n { println!("{}", dists[i][0] + dists[i][1]); } }