AOJ 1182 Railway Connection (ICPC Domestic 2012 D)
鉄道の最小コストを計算する問題。駅数が少ないのでワーシャル・フロイド法が使える。まず、会社ごとに各駅間の最短経路をワーシャル・フロイド法で計算し、対応する運賃も計算する。次に、各駅間の運賃を全会社の運賃の最小運賃として初期化して、ワーシャル・フロイド法で全駅間の最小運賃を計算する。
ワーシャル・フロイド法が使えるのでバグを作りにくいと思ったが、なぜか通らなくて一晩寝かせた。翌朝にデバッグをしようとしたときにサンプルケースの3個目があっていないことに気づいた。おそらく昨日もあっていなかったのだが、なぜかスルーしていた。元のコードの問題点は、同じ会社で同じ駅間に二つの路線があることを想定していなかったことだった。これを修正してAC。
通らなかった版の実装は40分くらい（それでも遅いが・・・）だった。サンプルケースの答えはちゃんと確認すべきですね・・・。
