水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

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

  • 問題

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

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

 

  • 解法

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

f:id:babcs2035:20180623151914p:plain

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

 

  • 解答

Submission #2716089 - AtCoder Regular Contest 061

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

f:id:babcs2035:20180623152213p:plain