ABC132-E Hopscotch Addict
概要
有向グラフG(N, M)が与えられ, グラフ上を一度の移動で3頂点進む. 頂点Sから頂点Tまで移動できる場合の最短経路を求める.
考察
頂点Sから頂点Tの経路かつ経路長が3の倍数であるもののうち, 最短のものを求めたい. 長さが3の倍数であるという制約を扱うために, 以下のようにグラフに遷移状態をもたせる.
A
B
C
D
A, 0
B, 1
C, 2
D, 0
このようにすることで(A, 0) => (D, 0)のパスの長さが3となる.
ここでD → Aのパスがあると仮定すると, 二週目は以下のようになる.
D, 0
A, 1
B, 2
C, 0
よって(A, 0) => (D, 0) => (C, 0)のパスが制約のもとで存在することがわかる.
このようにして(S, 0) => (T, 0) のパスが存在するかどうかを判定すればよい.
解答
遷移した回数をvとして, 0, 1, 2, 0, 1, ...の状態は v % 3で管理した.
use std::io;
use std::collections::VecDeque;
/// head comment
fn main() {
let (n, m) = {
let i = read::<usize>();
(i[0], i[1])
};
// line comment
let mut g = vec![Vec::new(); n];
for _ in 0..m {
let (u, v) = {
let i = read::<usize>();
(i[0] - 1, i[1] - 1)
};
g[u].push(v);
}
let (s, t) = {
let i = read::<usize>();
(i[0] - 1, i[1] - 1)
};
let mut que = VecDeque::new();
let mut dist = vec![vec![::std::usize::MAX; 3]; n];
que.push_back((s, 0));
while let Some((u, v)) = que.pop_front() {
if dist[u][v % 3] != ::std::usize::MAX { continue; }
dist[u][v % 3] = v;
for i in 0..g[u].len() {
let vv = g[u][i];
que.push_back((vv, v + 1));
}
}
if dist[t][0] != ::std::usize::MAX { println!("{}", dist[t][0] / 3); }
else { println!("-1"); }
}
Comments