子どもにふりかけの小袋を渡した。大切そうに 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"); } }
今日のコミット。