TopCoder SRM 677 Div2 Hard PalindromePath

もう終了して何時間も経ってるのに、まだ公式サイトに問題公開されてない。
https://community.topcoder.com/stat?c=problem_statement&pm=14100

問題

木を成す無向グラフが与えられる。
各辺にはアルファベットが１文字設定されている。

0番の頂点から1番の頂点まで、隣接する点を辿って到達したい。
その際、経由した辺の文字を連結した文字列が回文となるようにしたい。

条件を満たす最短距離を求めよ。

解法

回文ということは最初と最後は同じ文字の辺を用いることになる。
そこで0番と1番両方から同じ文字を辿って移動し、どこかで合流することを考えよう。

頂点s,tに対し、f(s,t)を0→s及び1→tを同じ文字の辺を辿って移動した場合の最短距離とする。
(s,t)に対し、s→x,t→yという同じ文字を持つ辺で移動可能な頂点(x,y)があれば、f(x,y)=f(s,t)+2となる。
よってダイクストラ法等でf(s,t)をそれぞれ求めよう。

あとはs==tであるようなf(s,t)またはs→tが辺をもつf(s,t)+1が解。

int dist[20][20];
char mat[20][20];

class PalindromePath {
	public:
	int shortestLength(int n, vector <int> a, vector <int> b, string c) {
		int i,j,x,y;
		
		ZERO(mat);
		FOR(i,a.size()) mat[a[i]][b[i]]=mat[b[i]][a[i]]=c[i];
		memset(dist,0x3f,sizeof(dist));
		
		queue<int> Q;
		dist[0][1]=0;
		Q.push(1);
		
		int mi=202020;
		
		while(Q.size()) {
			int k=Q.front();
			Q.pop();
			int cx=k/100;
			int cy=k%100;
			if(cx==cy) mi=min(mi,dist[cx][cy]);
			if(mat[cx][cy]) mi=min(mi,dist[cx][cy]+1);
			
			int tx,ty;
			FOR(tx,n) FOR(ty,n) if(mat[cx][tx] && mat[cx][tx]==mat[cy][ty]) {
				if(dist[tx][ty]>dist[cx][cy]+2) {
					dist[tx][ty]=dist[cx][cy]+2;
					Q.push(tx*100+ty);
				}
			}
		}
		if(mi>202000) return -1;
		return mi;
		
	}
}

まとめ

これはすんなり。