Time-8 - +K Roading

この問題は 01BFS を問います。

島 $a$ にいる時点での行動は、次のいずれかです。

• 島 $a+K$ をつなぐ橋を作る(魔法を $1$ 回使う) ...①
• 島 $a$ とつなぐ島 $p_1,p_2,...,p_n$ のいずれか $1$ つの島に行く(魔法は使わない) ...②

①について、この橋は魔法を使う必要があります。魔法を使うことで島 $a+K$ と隣接している島に移動することが可能となります。
②について、魔法を使わずに移動することが可能です。

こうしてみると、この問題は次の問題に帰着することができます。

• 有向グラフが与えられ、島と島をつなぐ辺には $0,1$ の重みが付加されている。
  このとき島 $A_i,B_i$ を互いにつなぐ辺には重み $0$ 、それ以外の辺※にはすべて重み $1$ が付加されている。
  島 $1$ から島 $N$ まで辺の上を移動することでたどり着くとき、歩いた辺の重みの総和の最小値を求めよ。

これは単一始点最短経路探索(ダイクストラ法など)問題に他なりません。しかし今回は $0,1$ のいずれかの重みが加えられているので、これは 01BFS といった探索法を用いることにより解くことができます。

計算量は $O(N+M)$ でこの問題を解くことができました。以下が解答例になります。

※「それ以外の辺」というのはある $1$ 以上 $N-K$ 以下の整数 $a$ であって、すべての辺の情報において $(A_i,B_i)\ne(a,a+K)$ が成り立つとき、島 $a,a+K$ を互いにつなぐ(仮想的な)橋をいいます。この橋を建設するのに魔法を $1$ 回要しますから、重み $1$ を付加してあげる必要があります。

追記: 想定解の修正をしました。島 $a$ から島 $a+K$ に橋を作ることはできますが、島 $a$ から島 $a-K$ には橋をかけることはできないことに注意してください。

• C++

• Python