第１５回日本情報オリンピック 予選 E - ゾンビ島 (Zombie Island)
問題概要
個の町と
本の町
を結ぶ道がある。この内の幾つかの町はゾンビに支配されており移動できず、そのような町から
本以下の道路を使って行き来できる町は危険な町である。
町を移動するたびに危険な町かそうでない町かに応じたコスト(問題中では宿泊費)を支払う時、町1から町まで行く時の最小費用を求める。
解法
まず、危険な町の列挙を行う。これは、Dijkstra法を良い感じに使うことによって実現できる。以下にその手法を示す。
手法
町全体の集合に対して、新たに町0を追加して考える。
まず、ゾンビに支配されている町に対しては、町0からその町へ距離0の有向辺を張る。
次に、入力で与えられる辺全てについてはその町同士に距離0の無向辺を張る。
上記の操作を完了した状態で、町0でDijkstra法を行うと、ゾンビに支配されている町には、町0から距離0の辺が伸びているため、最短距離が0で確定する。
それ以外の町については、町0からゾンビに支配されている町への最短距離が0であるから、危険な町からDijkstra法をしているのと同じことになる。つまり、町の町0からの最短距離というものは、町
に最も少ない本数の道を使って行き来できる、ゾンビに支配されている町からの最短距離を表すことになる。
つまり、これにより本以下で辿り着ける全ての町が列挙できた。
以上の操作により、危険な町とそうでない町が判別できるため、入力で与えられる辺の集合を順番に見て行き、辺が町を結ぶ辺である時、
\begin{eqnarray}
\left\{
\begin{array}{l}
A_iが危険な町ならA_iからB_iに対してコストQ、危険な町でないならコストPの無向辺を張る \\ B_iが危険な町ならB_iからA_iに対してコストQ、危険な町でないならコストPの無向辺を張る
\end{array}
\right.
\end{eqnarray}
という操作を行うことにより、移動する上でのコスト面での実装が終了する。
あとは町1からDijkstra法を行うことにより、町への最短距離が求まる。
長かったが、これを実装して、AC。
