Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 277 E問題 Crystal Switches

AtCoder ABC277 ABC E問題 500 pts

問題

提出解答

問題の概要

$N$ 頂点 $M$ 辺の単純無向グラフ $G=(V,E)$ がある. なお,

$V:=\{1,2, \dots, N\}$
$E:=\{u_j v_j \mid j=1,2, \dots, M\}$

である. また, 各辺は赤または青の色があり, $a_j=0$ ならば赤, $a_j=1$ ならば青である.

高橋君は最初, 頂点 $x$ にいるとき, $x$ と青い辺で接続している頂点に移動できる.

しかし, $K$ 個の頂点 $s_1, \dots, s_K$ にはスイッチがあり, スイッチがある頂点にいるとき, スイッチを押すことで高橋君が移動できる辺の色が入れ替わる (青から赤へ, 赤から青へ).

頂点 $1$ から適切な方法で頂点を移動し, スイッチを押すことで頂点 $N$ に到達することは可能か? 可能ならば頂点の移動回数の最小値を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$0 \leq K \leq N$
$1 \leq u_j v_j \leq N$
$G$ は単純無向グラフ
$a_j$ は $0$ または $1$
$1 \leq s_1 \lt \dots \lt s_K \leq N$

解法

高橋君の状況としては今いる頂点と通れる辺の色という $2N$ 通りの状態がありうる.

この $2N$ 個の状態に対して, $(v,R)$ で頂点 $v$ におり, 通れる辺の色が赤である状態, $(v,B)$ で頂点 $v$ におり, 通れる辺の色が青である状態を表す.

この $2N$ 個の状態を頂点とし, 次のように重み付きの辺を張ったグラフを $H$ とする.

$uv \in E$ に対して, 長さ $1$ の辺 $(u,X) (v,X)~(X=B,R)$ を張る.
$v \in V$ にスイッチがある場合, 長さ $0$ の辺 $(v,R) (v,B)$ を張る.

上の辺は移動すること, 下の辺はスイッチを押すことに対応する.

最初の状態は $(1,B)$ であることから, $H$ において, $(1,B)$ から $(N,R), (N,B)$ のうち少なくとも一方が到達可能であるか? そうであるならば距離の最小値が答えになる.

辺の重みが $0$ か $1$ なので, BFS におけるキューへの出し入れを工夫した 01-BFS を利用することによって計算量 $O(N+M)$ 時間で計算できる.