第15回日本情報オリンピック　予選５

2015年12月13日
情報オリンピック日本委員会

解説

この問題の解法は 2 つの段階からなる．1 つ目は危険な町を列挙する段階，2 つ目は宿泊費の合計が最小になる経路を見つける段階である．

危険な町を列挙するには，ゾンビが居る K 個のいずれかの町に S 本以内の道からなる経路で到達できる町を探さなければならない．単純な方法としては，ゾンビが居る K 個の町ごとに幅優先探索をすることである．この方法では KM に比例した時間がかかる．より良い方法としては，ゾンビが居る K 個の町それぞれと 1 本の道で結ばれている仮想の町を 1 つ考えて，そこから S+1 本以内の道からなる経路で到達できる町を列挙することである．このようにすれば 1 回の幅優先探索で危険な町をすべて列挙できる．

宿泊費の合計が最小になる経路を見つけるにはダイクストラ法やベルマンフォード法などといったアルゴリズムを使えば良い．これらのアルゴリズムは辺にコストがあるグラフに対する，ある 2 点間の最短経路を求めることに使えるアルゴリズムである．今回は辺ではなく頂点にコストがあるので少し工夫しなければならない．工夫の一つとして，双方向の辺を 2 つの有向辺にわけて，各有向辺のコストを向かっている頂点のコスト（宿泊費）と同じ値に設定する，というものがある．この場合，頂点 N に向かう辺のコストを 0 にするのを忘れてはいけない．

なおベルマンフォード法はダイクストラ法に比べてすこし時間が掛かるが3時間の競技時間内では充分間に合う．