AtCoder Regular Contest 061 : E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

• 問題

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

N 個の駅と M 個の路線があり、各路線には運営会社が決められている。同じ運営会社で連結の路線はどれだけ乗ってもコストはかからないが、運営会社をまたいで載る場合はコストがそれごとに１かかる。このとき、1 ~ N の最小コストを求める問題。

• 解法

改造ダイクストラで通そうとしたがどうしても通らなかったので、方針を変えた。各駅に「改札」（下図の□）をつくり、路線ごとに駅（下図の〇）を独立させた。「改札」から駅にいくにはコスト１の辺を張り、駅から「改札」にいくにはコスト０の辺を張る。

そうすれば、ただのダイクストラをやればいい。

• 解答

Submission #2716089 - AtCoder Regular Contest 061

6WA + 1RE もしてしまった。実行時間が TL の 3sec ギリギリでやばい。