ABC132 E問題：Hopscotch Addict

問題. Hopscotch Addict

有向グラフ と，頂点 が与えられる． から への移動回数の最小値を求めよ．ただし，任意の頂点 からの 1 回の移動とは， から距離がちょうど 3 離れた頂点へ移動することである（弧重みは 1）．また， から へ移動することができないときは -1 を出力せよ．

制約： ，　　（）

解法．最短経路問題

1 回の移動の定義が，距離がちょうど 3 ではなくちょうど1 離れた頂点へ移動することならば，この問題は有向グラフ上の最短経路問題である．ここでは，最短経路問題に帰着する．
頂点 に対して新たな頂点を として，弧 に対して新たな弧 を張った有向グラフ を考える．考えいている問題は 上で から への最短経路問題に等しく，最短距離は 3 で割った値となる．
弧重みは 1 なので幅優先探索で最短距離を求めることができ， の頂点数と弧数はそれぞれ と定数倍にしかならないので計算時間は である．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;


int main() {
    std::cin.tie(0); std::ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(3 * n);
    for (int i = 0, src, dst; i < m; ++i) {
        cin >> src >> dst;
        --src; --dst;
        for (int j = 0; j < 3; ++j)
            adj[3 * src + j].push_back(3 * dst + ((j + 1) % 3));
    }

    int s, t;
    cin >> s >> t;
    s = 3 * (s - 1); t = 3 * (t - 1);

    vector<int> dist(3 * n, -1);
    queue<int> que;
    dist[s] = 0; que.push(s);

    while (!que.empty()) {
        int cur = que.front(); que.pop();
        for (int dst : adj[cur]) {
            if (dist[dst] == -1 || dist[cur] + 1 < dist[dst]) {
                dist[dst] = dist[cur] + 1;
                que.push(dst);
            }
        }
    }

    if (dist[t] == -1) cout << dist[t] << '\n';
    else cout << dist[t] / 3 << '\n';

    return 0;
}

AOJによくある問題なので解けた．AtCoder で拡張グラフ上の最短経路問題を出すの珍しい．