Codeforces #436 Div2 F. Cities Excursions

ありそうで見たことない問題だった。
http://codeforces.com/contest/864/problem/F

問題

有向グラフが与えられる。
ここで以下のクエリに答えよ。

頂点SからTのパスを考える。
目的地であるTを除き同じ頂点は複数回通ってよい。
SからTに至るパスのうち、経由する頂点を並べると辞書順最短のものが存在する場合、K番目の要素を答えよ。

解法

クエリを目的地T別に処理しよう。
辺を逆順に辿り、Tに辿りうる頂点を列挙しよう。

各点からTに移動するとき、辞書順最短のパスを通るならTに辿りうる隣接点のうち最も番号の小さい頂点に移動するはずなので、その辺だけ残す。
こうすると、移動経路が一意に定まる。
後はダブリングの要領で(K-1)回移動した要素を求めよう。
ただし以下のコーナーケースに注意。

• 無限ループに落ち込む場合Tにたどり着けないので解なしを返す。
• (K-1)回未満の移動でTにたどり着いてしまう場合も解なしを返す。

int N,M,Q;
vector<int> E[3030];
vector<int> RE[3030];
int A[3030],B[13][3030];
int vis[3030];
vector<int> cand[3030];
int res[404040];
int S[404040],T[404040],K[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	scanf("%d%d%d",&N,&M,&Q);
	FOR(i,M) {
		scanf("%d%d",&x,&y);
		E[x-1].push_back(y-1);
		RE[y-1].push_back(x-1);
	}
	FOR(i,Q) {
		scanf("%d%d%d",&S[i],&T[i],&K[i]);
		S[i]--,T[i]--;
		cand[T[i]].push_back(i);
	}
	FOR(i,N) sort(ALL(E[i])), sort(ALL(RE[i]));
	
	MINUS(res);
	FOR(i,N) if(cand[i].size()) {
		ZERO(A);
		MINUS(B);
		
		queue<int> Q;
		Q.push(i);
		A[i]=1;
		while(Q.size()) {
			x=Q.front();
			Q.pop();
			FORR(e,RE[x]) if(A[e]==0) A[e]=1, Q.push(e);
		}
		B[0][i]=i;
		FOR(x,N) if(A[x]==1 && x!=i) {
			FORR(e,E[x]) if(A[e]==1) {
				B[0][x]=e;
				break;
			}
		}
		FOR(j,12) {
			FOR(x,N) if(B[j][x]>=0) B[j+1][x]=B[j][B[j][x]];
		}
		
		FORR(c,cand[i]) {
			int cur=S[c];
			if(A[cur]==0 || B[12][cur]!=i) continue;
			
			if(K[c]==1) {
				res[c]=cur+1;
				continue;
			}
			
			int num=K[c]-2;
			FOR(j,12) if(num&(1<<j)) cur=B[j][cur];
			
			if(cur==T[c]) continue;
			res[c]=B[0][cur]+1;
		}
		
		
	}
	
	FOR(i,Q) _P("%d\n",res[i]);
}

まとめ

方針はすぐ立ったけど、TLEやらMLEで意外に実装に手間取った。