blog.bouzuya.net

2024-02-13 ABC340 D

Figma でもらったデザインをチェックする場合には、各状態で妥当な表示になるかを確認する。一覧に一件もない状況や入力が省略されている状態などはド正常な状態だけをデザインされている場合には特に漏れがち。

新しい (?) メンバーに緊張した。


ABC340 : 鹿島建設プログラミングコンテスト2024(AtCoder Beginner Contest 340)

use std::{cmp::Reverse, collections::BinaryHeap};

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        abx: [(usize, usize, Usize1); n - 1],
    };

    let mut edges = vec![vec![]; n];
    for (i, (a, b, x)) in abx.into_iter().enumerate() {
        edges[i].push((i + 1, a));
        edges[i].push((x, b));
    }

    let inf = 1_usize << 60;
    let mut dist = vec![inf; n];
    let mut pq = BinaryHeap::new();
    pq.push((Reverse(0), 0));
    dist[0] = 0_usize;
    while let Some((Reverse(d), u)) = pq.pop() {
        if d > dist[u] {
            continue;
        }
        for (v, c) in edges[u].iter().copied() {
            if dist[v] > dist[u] + c {
                dist[v] = dist[u] + c;
                pq.push((Reverse(dist[v]), v));
            }
        }
    }

    let ans = dist[n - 1];
    println!("{}", ans);
}

今日のコミット。