けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 132 E - Hopscotch Addict (青色, 500 点)

グラフの頂点を倍加するタイプの問題ですね。

問題へのリンク

問題概要

 N 頂点  M 辺の有向グラフが与えらえます。頂点  S から頂点  T へと、けんけんぱで移動したいものとします。

1 回のけんけんぱでは、「自分の今いる頂点から出ている辺を 1 つ選んで、その辺が接続する頂点に移動する」という操作をちょうど 3 回連続で行います。

ちょうどピッタリ  T で止まるのに必要な操作回数の最小値を求めてください。不可能な場合は -1 を出力してください。

制約

  •  2 \le N \le 10^{5}
  •  1 \le M \le 10^{5}

考えたこと

つまり、


  •  S から  T への路であって、
  • 長さが 3 の倍数であるもののうち
  • 最短なものを求めよ

という問題であるといえます。「長さが 3 の倍数である」という制約を扱うために、グラフを拡張します。もともとのグラフの

  • 頂点 v

  • (v, 0)
  • (v, 1)
  • (v, 2)

というふうに拡張します。グラフの頂点数は 3 倍になります。そしてもとのグラフの辺 u -> v については

  • (u, 0) -> (v, 1)
  • (u, 1) -> (v, 2)
  • (u, 2) -> (v, 0)

という風に貼り直します。この新しいグラフ上で (S, 0) -> (T, 0) となるようなパスがあれば、このパスの長さは 3 の倍数であることを保証されます。つまり拡張したグラフにおいて、


(S, 0) から出発して、(T, 0) へと至るまでの最短経路


を BFS で求めればよいです。計算量は  O(N + M) となります。

コード

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

using Graph = vector<vector<int>>;
using pint = pair<int,int>;

int N, M;
Graph G;
int s, t;

long long solve() {
    vector<vector<long long>> dist(N, vector<long long>(3, -1));
    dist[s][0] = 0;
    queue<pint> que;
    que.push({s, 0});
    while (!que.empty()) {
        pint cur = que.front(); que.pop();
        int v = cur.first;
        int parity = cur.second;
        for (auto nv : G[v]) {
            int np = (parity + 1) % 3;
            if (dist[nv][np] == -1) {
                dist[nv][np] = dist[v][parity] + 1;
                que.push({nv, np});
            }
        }
    }
    if (dist[t][0] == -1) return -1;
    else return dist[t][0] / 3;
}

int main() {
    cin >> N >> M;
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        G[u].push_back(v);
    }
    cin >> s >> t;
    --s, --t;
    cout << solve() << endl;            
}