読者です 読者をやめる 読者になる 読者になる

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

AtCoder 競プロ

問題

arc061.contest.atcoder.jp

考察

こういう1つのノードが複数の状態を持つグラフは、状態ごとにノードを分割してあげると上手くいくことが多いかと思います。
今回もご多分にもれず、駅と会社の2つをペアで考えてみます。

各行では駅2つと会社が与えられるので、これらのノードをコスト0のエッジで繋げると、タダで移動できる路線の出来上がりです。

さて、このままでは他の会社の路線を利用できないので、少し工夫が必要です。
ここで現実世界に即して考えると、改札を出て「どの会社のものでもない駅」に移動すると考えられます。
そこで、会社0の駅を作り、どの会社の同じ駅もここに通じるようにしてしまいます。
これにより、普通に最短経路を求めることで、駅間の最小コストが求まります。
なお、辺のコストは、会社nから会社0の駅移動は0、会社0から会社nの駅移動は1とすると自然です。

実装上の工夫

通常のdijkstraでは配列でグラフや距離を持ちますが、今回は制約上全てのパターンを持つことができません。
そこで、hashを使うデータ構造に押し込み、要素数 O(N+M)かつ O(1)で取り出せるようにします。

C++ではunordered_mapを使うと速いです。
というより、mapだと速度が足りませんでした。
以下のように全く結果が異なります。

  • map => TLE
  • グラフだけunordered_map => 2.3s
  • グラフと距離をunordered_map => 1.7s

また、駅と会社のペアは、座標の処理でよくあるように1つの64bit整数に詰め込んでしまうと少し楽に処理ができます。

コード

ll pl(ll a, ll b) {
    return a * ((ll)1e6+10) + b;
}

using edge = pair<ll, int>;

int dijkstra(int start, int goal, unordered_map<ll, vector<edge> >& graphs) {
    priority_queue< pair<int, ll>,
            vector< pair<int, ll> >,
            greater< pair<int, ll> > > que;
    unordered_map<ll, int> d;
    d[pl(start, 0)] = 0;
    que.push(mp(0, pl(start, 0)));

    while(!que.empty()){
        pair<int, ll> p2 = que.top(); que.pop();
        int p = p2.first;
        ll v = p2.second;

        if(d[v] == 0 && v != pl(start,0))
            d[v] = INF;
        if(d[v] < p)
            continue;

        tr(it, graphs[v]) {
            const ll to = it->first;
            const int cost = it->second;
            if(d[to] == 0 && to != pl(start, 0))
                d[to] = INF;

            if(d[to] > d[v] + cost) {
                d[to] = d[v] + cost;
                que.push(mp(d[to], to));
            }
        }
    }

    return d[pl(goal,0)];
}

int main() {
    int N, M;
    cin >> N >> M;

    unordered_map<ll, vector<edge> > graph;
    while(M--){
        int p, q, c;
        cin >> p >> q >> c;
        --p, --q;

        graph[pl(p, c)].push_back(mp(pl(q, c), 0));
        graph[pl(q, c)].push_back(mp(pl(p, c), 0));

        // core station
        graph[pl(p, c)].push_back(mp(pl(p, 0), 0));
        graph[pl(p, 0)].push_back(mp(pl(p, c), 1));
        graph[pl(q, c)].push_back(mp(pl(q, 0), 0));
        graph[pl(q, 0)].push_back(mp(pl(q, c), 1));
    }

    int d = dijkstra(0, N-1, graph);
    if(d == 0)
        cout << -1 << endl;
    else
        cout << d << endl;

    return 0;
}

備考

グラフの変形、実装の工夫が多く楽しい問題だと思いますが、↑の方法だと速い言語でしか通らなさそうな。