へろへろだ。疲れている。寒くなったせいかも。

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
  • Add infra::firestore_store mod
• rust-atcoder 1 commit
  • abc192 e