ABC340 D

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

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

---

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

• D - Super Takahashi Bros. https://atcoder.jp/contests/abc340/tasks/abc340_d
  • 提出: https://atcoder.jp/contests/abc340/submissions/50252766
  • 最短経路問題
  • N 個の頂点のうち N 番目以外の N - 1 個の頂点 i からは i + 1 とそれ以外の頂点 1 つに辺が延びていると考える
  • 素朴にダイクストラ法などで N までの最短経路について考えればいい

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);
}

---

今日のコミット。

• bbna 2 commits
  • Run cargo update
  • Add DELETE /invalid_expo_push_tokens endpoint
• rust-atcoder 1 commit
  • abc340 d