Hopscotch Addict [AtCoder Beginner Contest 132 E]

https://atcoder.jp/contests/abc132/tasks/abc132_e

前提知識

• BFS

解説

https://atcoder.jp/contests/abc132/submissions/6191952

問題の解き口が分からない場合は、より簡単な問題に取り組むのも方針の1つである。
今回はけんけんぱだから難しいのであり、ただ移動するときのアルゴリズムを考える。
これは単純なBFSで解けそうである。
　
より簡単な問題の解法をベースとして、今回の問題を考えてみる。
前の問題では、状態として、どの頂点に到達したときの最短距離を考えていたが、
これを「どの頂点に何歩目で到達したときの最短距離」として考える。
つまり、
dst[cu][jmp] := 頂点cuにjmp歩目で到達したときの最短距離
のように状態を定義して、BFSをすればいい。
これは状態数が3Nであるため、計算量は簡単な方の問題と変わらない。

int N, M;
vector<int> E[101010];
int S, T;
ll dst[101010][3];
int vis[101010][3];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a, b; cin >> a >> b;
		a--; b--;
		E[a].push_back(b);
	}
	cin >> S >> T; S--; T--;

	queue<pair<int, int>> que;

	que.push({ S, 0 });
	vis[S][0] = 1;

	while (!que.empty()) {
		int cu, jmp;
		tie(cu, jmp) = que.front(); que.pop();

		if (cu == T and jmp == 0) {
			cout << dst[cu][jmp]/3 << endl;
			return;
		}

		int jmp2 = (jmp + 1) % 3;
		fore(to, E[cu]) if (!vis[to][jmp2]) {
			vis[to][jmp2] = 1;
			dst[to][jmp2] = dst[cu][jmp] + 1;
			que.push({ to, jmp2 });
		}
	}

	cout << -1 << endl;
}