AtCoder ABC #132 : E - Hopscotch Addict

Dまでは順調だったのにね。
https://atcoder.jp/contests/abc132/tasks/abc132_e

問題

N頂点の有向グラフが与えられる。
頂点SからTに移動することを考える。
1手で、辺に沿って移動するということを3回連続で行う。
途中でTを経由しても、そこで止まることはできない。

Tに至る最小移動回数は何回か。

解法

各頂点において、そこに至る最小到達移動位回数をmod 3で分けて考える。
あとは頂点が(N*3)個あると思ってダイクストラ法なりなんなりで最短経路問題を解こう。

int N,M;
vector<int> E[101010];
int S,T;

int D[101010][3];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--;y--;
		E[x].push_back(y);
	}
	cin>>S>>T;
	S--,T--;
	FOR(i,N) D[i][0]=D[i][1]=D[i][2]=1<<30;
	queue<int> Q;
	D[S][0]=0;
	Q.push(S*3);
	while(Q.size()) {
		int cur=Q.front()/3;
		int m=Q.front()%3;
		int n=(m+1)%3;
		Q.pop();
		FORR(e,E[cur]) {
			if(D[e][n]>D[cur][m]+1) {
				D[e][n]=D[cur][m]+1;
				Q.push(e*3+n);
			}
		}
	}
	
	if(D[T][0]<1<<30) cout<<D[T][0]/3<<endl;
	else cout<<-1<<endl;
	
}

まとめ

無向グラフだと勘違い…。