AtCoder Regular Contest 061 E - すぬけ君の地下鉄旅行

お題箱より。

E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

解法

グラフの最短路問題として解けそうではありますが、異なる運営会社間での乗り換えを考慮する必要があります。つまり「どの駅にいるか」だけでなく、「その駅でどの会社の路線に乗っているか」という情報が必要になります。

このようなときに、「駅 にいて会社 の路線に乗っている」という状態をペア として、このペアそれぞれを1つの頂点としてグラフを作るテクニックがあります。こうすれば電車での駅間の移動や乗り換えのコストを正しく扱うことができます。同じ駅かつ違う会社の頂点に乗り換えるときにコスト1が掛かると思えばよいです。

このように状態を組み合わせるときは頂点の個数がものすごく大きな数にならないか気を付ける必要がありますが、今回は2駅間を繋ぐ路線が 個与えられることから、この頂点数は最大でも全部で 個です。

ただしこの方針で全ての乗り換えパターンに辺を張ってしまうと、大量の路線が乗り入れる駅があったときに辺数がものすごい数になってしまいます。

これは困るのでもう少し工夫しましょう。乗り換えを、「改札を出る」動きと「次の路線の改札に入る」動きに分類します。そして「改札の外」を表す頂点をさらに追加します。

このようにすると、辺数が頂点数の2倍で抑えられます。今までは無向グラフとして扱えていましたが、この時点でグラフが有向グラフになっていることに注意してください。

あとはこのグラフ上でダイクストラ法などを回せば答えを求めることができます。辺のコストが0または1なので01-BFSでも良いですね。

ACコード

Submission #5571322 - AtCoder Regular Contest 061

（リクエストくれた人の言語が分からなかったのでC++にしています…RubyかPythonなら書けるので必要なら言ってください）

実装に関してですが、駅番号と会社番号（「改札の外」の場合は-1としています）のペアを頂点として扱う必要があります。しかもこれらの頂点の距離などを2次元配列などで管理すると、スカスカでサイズの大きな配列が必要になってしまいます。

実装方針は色々あると思いますが、いったん使う頂点をペアとして列挙し、重複を排除した後に「座標圧縮」の要領でペアに番号を振ってしまうのが分かりやすいと思います。ここでペアから頂点番号を逆引きできるmapなども作っておくと楽です。

新しく振った番号で辺を全て張り直してしまえばあとはこっちのものです、普通にダイクストラ法や01-BFSをすればよいです。上記リンク先のコードでは01-BFSにしています。