ABC132 E - Hopscotch Addict (500)

E - Hopscotch Addict

概要

有向グラフが与えられる。始点Sから終点Tまでの経路で長さ3がの倍数のもののうち最小のものについて、その長さを3で割ったものを出力せよ。（けんけんぱで移動できるか）

制約

2 ≦ N ≦ 10^5
0 ≦ M ≦ min(10^5, N * (N - 1))

方針

グラフ上の探索を行う。訪れた頂点をメモすることで計算量を減らしたいが、3の倍数で到着できるかどうかがネックなので1度訪れた頂点をメモするだけだと正解の方法を排除してしまう可能性がある。

メモの方法を少し工夫する。
ある頂点に到達した際の移動回数を記憶しておき、それをmod 3した数値が異なる場合は別の移動と考える。
これで全ての移動を確認することが出来る。

感想

最初に思いついたのは「移動回数が3の倍数の時だけメモする」だが、これだとTLE。
Submission #6190952 - AtCoder Beginner Contest 132

解答

Submission #6195729 - AtCoder Beginner Contest 132

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int max_n = 300015;
int N, M;
int S, T;
vector<vector<int>> g(max_n, vector<int>());
vector<bool> used(max_n, false);
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N >> M;
 
	rep(i, M){
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		g[u].push_back(v + N);
		g[u + N].push_back(v + 2 * N);
		g[u + 2 * N].push_back(v);
	}
 
	cin >> S >> T;
	S--;
	T--;
 
	queue<int> q1, q2;
	q1.push(S);
	q2.push(0);
 
	while(q1.size() > 0){
		// cout << q1.front() << "," << q2.front() << endl;
		int x = q1.front();
		q1.pop();
 
		int cnt = q2.front();
		q2.pop();
 
		if(x == T){
			cout << cnt / 3 << endl;
			return 0;
		}
 
		for(int y : g[x]){
			if(!used[y]){
				used[y] = true;
				q1.push(y);
				q2.push(cnt+1);
			}
		}
	}
 
	cout << -1 << endl;
}