Kazun の競プロ記録

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

AtCoder Beginner Contest 257 F問題 Teleporter Setting

AtCoder ABC ABC257 F問題 500 pts

問題

提出解答

問題の概要

無向グラフ $G=(V,E)$ が以下で与えられる.

$V:=\{0,1, \dots, N\}$
$E:=\{U_j V_j \mid j=1,2, \dots, M\}$

$i=1,2, \dots, N$ に対して, 頂点 $0$ と頂点 $N$ を同一視したグラフを $G_i$ とする.

このとき, $i=1,2,\dots, N$ に対して, 以下の問 $i$ に答えよ.

$G_i$ 上で, 頂点 $1$ と頂点 $N$ は連結か? 連結ならば $G_i$ 上で頂点 $1$ , 頂点 $N$ 間の距離を求めよ.

制約

$2 \leq N \leq 3 \times 10^5$
$1 \leq M \leq 3 \times 10^5$
$0 \leq U_j \lt V_j \leq N$
$j \neq k \Rightarrow (U_j, V_j) \neq (U_k, V_k)$

解法

問 $i$ における問題の解答は, 以下と同じである.

$G$ に長さ $0$ の辺 $0i$ を加えたグラフを $H_i$ とする. このとき, $H_i$ 上で, 頂点 $1$ と頂点 $N$ は連結か? 連結ならば $H_i$ 上で頂点 $1$ , 頂点 $N$ 間の距離を求めよ.

この問題を解くことにする. このとき, $H_i$ 上の頂点 $1$ から頂点 $N$ へのパスは次のうちのどれかに該当する.

長さ $0$ の辺 $0i$ を使わないパス.
長さ $0$ の辺 $0i$ を使い, そのうち, 頂点 $0$ から頂点 $i$ の向きに移動するパス.
長さ $0$ の辺 $0i$ を使い, そのうち, 頂点 $i$ から頂点 $0$ の向きに移動するパス.

グラフ $G$ 上の2頂点 $u,v$ 間の距離を $d(u,v)$ , グラフ $H_i$ 上の2頂点 $u,v$ 間の距離を $d_i(u,v)$ と書くことにする.

すると, それぞれの場合における長さの最小値上から順に,

$d(1,N)$
$d(1,0)+d(i,N)$
$d(1,i)+d(0,N)$

であるから,

$d_i(1,N)=\min (d(1,N), d(1,0)+d(i,N), d(1,i)+d(0,N))$

であることがわかる.

よって, $d_i(1,N)$ を求めるためには $d(1, \bullet), d(\bullet, N)$ が分かればよいことがわかるので, それぞれを 01-BFS で求めることによって求めることができる.

01-BFS の時間計算量が $O(N+M)$ であり, この前計算のもとで $d_i(1,N)$ は各 $i$ に対して $O(1)$ で求められるので, 全体で $O(N+M)$ 時間で求められる.

補足

付け加える辺の長さを $0$ ではなく $1$ にして 01-BFS の部分を単純な BFS にしても実は正解を導くことが証明できる.