[AtCoder] ABC 132 E – Hopscotch Addict

2019年6月30日2019年7月1日

問題

方針

ステップ数が \( 3 \) の最短距離の探索

例えば、ステップ数が \( 3 \) の最短経路の探索では、スタート地点から \( 3 \) ステップ目で到達可能な頂点を距離 \( 1 \) で到達可能な頂点とします。また、この到達した頂点から探索を行います。この探索において、\( i \) ステップ目で訪れた頂点 \( j \) のフラグを \( f_{i, j} \ (1 \leq i \leq 3 \wedge 1 \leq j \leq N)  \) とします。\( f_{3, T} = 1 \) ならば、到達可能です。

幅優先探索を行うことを考えます。\( S \) から \( i \) までの最短距離を \( d_i \) とます。キュー \( q \) に \( S \) を入れます。そして、\( f_{3, S} = 1 \) とします。

頂点 \( S \) から \( 1 \) ステップで行くことができる頂点 \( i \) のフラグ \( f_{1, i} \) を調べ、フラグが立っていなければ探索を止めて、そうではなければ探索を続け、その頂点 \( i \) に訪れます。つぎに、\( i \) から \( 1 \) ステップで行くことができる頂点 \( j \) のフラグ \( f_{2, j}\) を調べ、フラグが立っていなければ探索を止め、そうではなければ探索を続け、その頂点 \( k \) に訪れます。\( f_{3, k} = 0 \) であれば、\( d_k = d_i + 1 \) とします。そして ( q \)  に \( k \) を挿入します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  int u[M], v[M];
  for (int i = 0; i < M; i++) {
    cin >> u[i] >> v[i];
    u[i]--;
    v[i]--;
  }
  int S, T;
  cin >> S >> T;
  S--;
  T--;
  vector<int> adj[N];
  for (int i = 0; i < M; i++) {
    adj[u[i]].push_back(v[i]);
  }
  deque<int> q;
  q.push_back(S);
  int d[N];
  int INF = 1000000000;
  for (int i = 0; i < N; i++) {
    d[i] = INF;
  }
  d[S] = 0;
  int vis[N]{};
  vis[S] = 1;
  int cnt = 0;
  int vis1[N]{};
  int vis2[N]{};
  while(!q.empty()) {
    int t = q.front();
    q.pop_front();
    for (int i : adj[t]) {
      if (vis1[i] == 1) continue;
      vis1[i] = 1;
      for (int j : adj[i]) {
        if (vis2[j] == 1) continue;
        vis2[j] = 1;
        for (int k : adj[j]) {
          if (vis[k] == 0) {
            vis[k] = 1;
            d[k] = d[t] + 1;
            q.push_back(k);
          }
        }
      }
    }
  }
  if (d[T] != INF) {
    cout << d[T] << "\n";
  } else {
    cout << "-1";
  }
  return 0;
}