2023-05-12 ふりかけの小袋 / ABC068 C を解いた

子どもにふりかけの小袋を渡した。大切そうに 3 回に分けて使っていた。良い。

(nostr に投稿済み)

ABC068 C - Cat Snuke and a Voyage (AtCoder Beginner Contest 068 問題) https://atcoder.jp/contests/abc068/tasks/arc079_a
- https://atcoder.jp/contests/abc068/submissions/41325020
- グラフ, 最短経路
- 1 から N までが距離 2 か
- 幅優先探索で距離 2 以下を探しても良さそうだけど、 0 から到達可能な点の距離をすべて求めた

use std::collections::VecDeque;

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

fn adjacency_list(n: usize, uv: &[(usize, usize)]) -> Vec<Vec<usize>> {
    let mut e = vec![vec![]; n];
    for (u, v) in uv.iter().copied() {
        e[u].push(v);
        e[v].push(u);
    }
    e
}

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

    let edges = adjacency_list(n, &ab);
    let inf = n + 1;
    let mut dist = vec![inf; n];
    let mut deque = VecDeque::new();
    deque.push_back(0);
    dist[0] = 0;
    while let Some(u) = deque.pop_front() {
        for v in edges[u].iter().copied() {
            if dist[v] == inf {
                dist[v] = dist[u] + 1;
                deque.push_back(v);
            }
        }
    }
    if dist[n - 1] == 2 {
        println!("POSSIBLE");
    } else {
        println!("IMPOSSIBLE");
    }
}

今日のコミット。