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

問題

https://atcoder.jp/contests/arc061/tasks/arc061_c

考え方

まずは問題文の条件通り、路線ごとの駅にノードを対応させてグラフを構築する。駅と会社でそれぞれの頂点の役割が変わってくるので座圧の要領で拡張点に index を付与しておく。

同じ駅で会社が異なる場合はそれぞれ乗り換えすることができるが、単純に各駅に辺を張ると最大で O(会社²) の辺がはられることになり間に合わない。そこで各駅の代表駅のような駅を追加し、代表駅から各会社の同一の駅に辺を張ることで辺の数を O(会社) にする。これがこの問題の本質だと思う。

そのように考えると代表駅からそれぞれの駅に入る場合はコスト 1 の辺、駅から代表駅に出る場合はコスト 0 の辺を張ることになる。また M 本の辺は同じ会社の駅であるからそれぞれの駅についてコスト 0 の辺を張ることになる。このグラフにおいて駅 1 の代表駅からダイクストラ法をして、駅 N の代表駅への最短のコストが解になる。

イメージ図は以下。

実装上の面倒な点としてはそれぞれの頂点に index を張ることである。今回は駅 i で会社 c の場合に以下のようにして index を取るようにした。

       long f(int i, int c) {
            return (long)c << 32 | i;
        }

        void addId(long key) {
            if (map.containsKey(key)) return;
            map.put(key, ++id);
        }

        int getId(long key) {
            return map.get(key);
        }

Submission #4225861 - AtCoder Regular Contest 061

どこに着目して考察するべきだったか

だいたい拡張グラフのダイクストラ法だが、ボトルネックを解消するように別の頂点を構築する、という発想が必要。

何がバグっていたか

得た知見(典型ポイント)

• グラフ上の頂点を拡張してダイクストラ法
• グラフの頂点を座圧

類題