HackerRank University CodeSprint 5 : F. Interesting Trip

これ通っちゃっていいんかな。
https://www.hackerrank.com/contests/university-codesprint-5/challenges/marmelade-kingdom

問題

DAGを成すグラフが与えられる。
各頂点はアルファベット１文字が設定されている。
ここで、始点と終点が指定される。始点から終点に至るパスのうち、経由した頂点のアルファベットを並べた文字列の辞書順最小値を求めよ。

解法

まずグラフを逆向きに辿り、終点に遷移可能な点を列挙しておく。
以後、始点から初めて同じ文字列を生成するケースにおける頂点のsetを更新していくことを考える。
あとは辞書順最小値を求める典型パターンの通り、現在の頂点のsetから遷移できる頂点群のうち、文字列順最小の文字を持つ頂点群があればそのsetに遷移する、ということを繰り返す。
途中終点に到達したら、遷移元を逆向きに辿り経路を復元しよう。
このアプローチ、O(VE)ぐらいかかりそうな気がしたのだけど通ってしまった。

int N,M,A,B;
string S;
vector<int> E[202020],RE[202020],C[202020][26];
int ok[202020],D[202020],pre[202020];
vector<int> cand;
vector<int> ncand;
queue<int> Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		RE[y-1].push_back(x-1);
	}
	cin>>A>>B;
	A--,B--;
	
	ok[B]=1;
	Q.push(B);
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		FORR(e,RE[x]) if(ok[e]==0) ok[e]=1, Q.push(e);
	}
	if(ok[A]==0) return _P("No way\n");
	
	FOR(i,N) {
		FORR(e,E[i]) if(ok[e]) C[i][S[e]-'a'].push_back(e);
		D[i]=202020;
	}
	
	cand.push_back(A);
	int d=0;
	D[A]=0;
	while(1) {
		if(count(ALL(cand),B)) break;
		d++;
		
		ncand.clear();
		FOR(i,26) {
			FORR(c,cand) FORR(e,C[c][i]) if(D[e]!=d) D[e]=d, pre[e]=c,ncand.push_back(e);
			if(ncand.size()) break;
		}
		swap(cand,ncand);
		
	}
	
	string ret;
	while(B!=A) ret+=S[B], B=pre[B];
	ret+=S[A];
	reverse(ALL(ret));
	cout<<ret<<endl;
	
}

まとめ

これ想定解なのかな？