へろへろだ。疲れている。寒くなったせいかも。
SOMPO HD プログラミングコンテスト2021(ABC192 : AtCoder Beginner Contest 192)
- E - Train
https://atcoder.jp/contests/abc192/tasks/abc192_e
- 提出: https://atcoder.jp/contests/abc192/submissions/47427639
- 最短経路問題をひとひねりしたもの
- 辺が素直に貼られていないだけで、各都市への最短時間を求めれば良いことに変わりはない
- その都市から各鉄道について次の時間を待って移動すれば良い
use std::{cmp::Reverse, collections::BinaryHeap}; use proconio::{input, marker::Usize1}; fn main() { input! { n: usize, m: usize, x: Usize1, y: Usize1, abtk: [(Usize1, Usize1, usize, usize); m] }; let mut edges = vec![vec![]; n]; for (a, b, t, k) in abtk { edges[a].push((b, t, k)); edges[b].push((a, t, k)); } let inf = 1_usize << 60; let mut time = vec![inf; n]; let mut pq = BinaryHeap::new(); pq.push((Reverse(0_usize), x)); time[x] = 0_usize; while let Some((Reverse(t), u)) = pq.pop() { if t > time[u] { continue; } for (v, t, k) in edges[u].iter().copied() { let nt = if time[u] % k == 0 { time[u] } else { time[u] + k - (time[u] % k) } + t; if nt < time[v] { time[v] = nt; pq.push((Reverse(nt), v)); } } } let ans = time[y]; if ans == inf { println!("-1"); } else { println!("{}", ans); } }
今日のコミット。
- kireta 1 commit
- rust-atcoder 1 commit