blog.bouzuya.net

2023-07-26 bouzuya/genpi をつくった / ABC191 E を解いた

bouzuya/genpi 0.3.0 をつくった。

いつもの BASE_PATH 設定を入れた。 https://bouzuya.net/lab/... からアクセス可能にする関係で欲しくなる。

crates:temp-env を試してみた。テスト時に環境変数を設定するものでテストの失敗時に環境変数を戻せるようになっている……とのこと。どことなく使いづらいインタフェースだけど導入した。

ABC191 : AtCoder Beginner Contest 191

  • E - Come Back Quickly https://atcoder.jp/contests/abc191/tasks/abc191_e
    • 提出: https://atcoder.jp/contests/abc191/submissions/43959534
    • 嘘解法 (?) で通した
    • 各頂点を開始位置として走査する
    • 開始位置ごとに各頂点への最短距離をダイクストラ法で求め、その過程でその頂点から開始位置に遷移できる場合は最短距離+その距離の最小値を求めておく
    • ダイクストラ法で走査対象とならない頂点は開始位置から到達不可能な頂点なので無視していい
    • 最短経路の頂点から複数の頂点を経由して戻るケースでも問題ない。往路で経由しているならその頂点から開始位置に戻るほうが短くなり往路で経由していないならその頂点への最短距離は復路の距離になる (ので、どちらでもその経由する頂点の最短距離を求める際に計算して良い)
use std::{cmp::Reverse, collections::BinaryHeap};

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

fn main() {
    input! {
        n: usize,
        m: usize,
        abc: [(Usize1, Usize1, usize); m]
    };

    let edges = {
        let mut edges = vec![vec![]; n];
        for (u, v, w) in abc.iter().copied() {
            edges[u].push((v, w));
        }
        edges
    };
    let inf = 1_usize << 60;

    for s in 0..n {
        let mut min_dist: Option<usize> = None;
        let mut dist = vec![inf; n];
        let mut pq = BinaryHeap::new();
        dist[s] = 0;
        pq.push(Reverse((0, s)));
        while let Some(Reverse((w_u, u))) = pq.pop() {
            if w_u > dist[u] {
                continue;
            }
            for (v, w_v) in edges[u].iter().copied() {
                if v == s {
                    min_dist = Some(match min_dist {
                        Some(m) => m.min(w_u + w_v),
                        None => w_u + w_v,
                    });
                    continue;
                }
                let w = w_u + w_v;
                if w < dist[v] {
                    dist[v] = w;
                    pq.push(Reverse((w, v)));
                }
            }
        }

        println!("{}", min_dist.map(|ans| ans as i64).unwrap_or(-1));
    }
}

今日のコミット。