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

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

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

こういうのを僕が初めて解いたのは、はまづさんのこの問題だった。

atcoder.jp

そして、昔の ICPC などでは特に、この手の問題は何度も何度も出題されていた。

問題へのリンク

問題概要

 N 頂点  M 辺の有向グラフが与えらえる。頂点  S から頂点  T へと、けんけんぱで移動したいです。 1 回のけんけんぱでは、「自分の今いる頂点から出ている辺を 1 つ選んで、その辺が接続する頂点に移動する」という操作をちょうど 3 回連続で行います。

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

制約

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

考えたこと

つまり、


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

という問題である。基本的には BFS でよいのだが、この「長さが 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 で求めれば OK。

#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;            
}