AtCoder ABC #197 : F - Construct a Palindrome

まぁこれは定番かな…。
https://atcoder.jp/contests/abc197/tasks/abc197_f

問題

N頂点M辺の無向グラフが与えられる。
各辺には文字が設定されている。
1番の頂点からN番の頂点まで辺に沿って移動することを考える。
通過した辺の文字を順に並べた文字列が回文となるような最短経路の長さを求めよ。

解法

dp(u,v) := u→vに移動する経路のうち、通過した辺の文字を順に並べた文字列が回文となる最短の経路の長さ
とする。dp(1,N)が解。
dp(x,x) = 0は自明だし、x-y間に辺がある場合dp(x,y)=1も自明。
あとはそこから両端を伸ばしていくことを考えよう。

dp(x,y)がわかっているとき、同じ文字を持つx-sとy-tという辺の対があるなら、dp(s,t)=dp(x,y)+2となる。
あとはダイクストラの要領でdp(x,y)を短い順に埋めて行こう。

int N,M;
vector<int> E[1010][26];
int D[1010][1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(x,N) FOR(y,N) D[x][y]=(x==y?0:1LL<<30);
	FOR(i,M) {
		cin>>x>>y>>s;
		E[x-1][s[0]-'a'].push_back(y-1);
		E[y-1][s[0]-'a'].push_back(x-1);
		if(x!=y) D[x-1][y-1]=D[y-1][x-1]=1;
	}
	
	queue<int> Q;
	FOR(i,N) Q.push(i*1000+i);
	FOR(x,N) FOR(y,N) if(D[x][y]==1) Q.push(x*1000+y);
	
	while(Q.size()) {
		int u=Q.front()/1000;
		int v=Q.front()%1000;
		Q.pop();
		if(u==0&&v==N-1) {
			cout<<D[u][v]<<endl;
			return;
		}
		FOR(i,26) {
			FORR(x,E[u][i]) FORR(y,E[v][i]) {
				if(D[x][y]>D[u][v]+2) {
					D[x][y]=D[u][v]+2;
					Q.push(x*1000+y);
				}
			}
		}
		
		
	}
	
	cout<<-1<<endl;

}

まとめ

そうか、今後はsponsoredでも賞金がない回が出てくるのか。