TopCoder SRM 492 SRM Div1 Medium TimeTravellingTour

問題

N個の都市がいくつかの道でつながっている。
それぞれの道がどの都市をつなぎ、どれくらいの長さであるかが与えられる。


Gogoはcities[i]で表される都市を全て訪問したい。
cities[i]の都市はこの順に訪問する必要がある。(ただし、別の都市の通り道として、訪問せずに経由することもできる)


また、Gogoはタイムマシーンを持っていて、今までに通った都市に時間0で戻ることができる。
ただし、タイムマシーンで一度戻った後で、逆方向にタイムマシーンを使うことはできない。すなわち、A,B,C,D,Eと都市を通り、タイムマシーンでCに戻った後はタイムマシーンでDやEへ行くことはできない。(AやBへ行くことは可能)


このとき、全ての都市を訪問するのにかかる時間を求めよ。
都市の訪問を終了したとき、Gogoはどの都市にいてもよいものとする。

制約条件

N≦50
訪問する都市の数≦50

方針

動的計画法による。
dp[i][l][r]を、現在都市iにいて、訪問リストのj番目の都市からk番目の都市を全て訪問するのにかかる時間とする。


すると、dp[i][l][r]は、iからcities[l]へ行って、l+1からrを訪問する仕方と、
都市jまで一旦行き、リストのm(j≦m≦k)番目の都市mへ行って、jまでタイムマシンで戻り、jからm+1番目の都市からr番目の都市まで訪問する仕方の二つに分けられる。


それぞれの場合は、より小さい部分問題になっているため、
これをメモ化して更新していくようなO(N^5)の動的計画法により解ける。


定数倍がやや厳しく、再帰で書くとTLEした。

ソースコード

ll dp[50][51][51];
ll d[50][50];
class TimeTravellingTour {
	public:
	long long determineCost(int N, vector <int> C, vector <string> roads) 
	{
		rep(i,N)rep(j,N)d[i][j]=i==j?0:INF;
		string s=accumulate(all(roads),string());
		rep(i,s.size())if(s[i]==',')s[i]=' ';
		stringstream ss(s);
		int a,b,c;
		while(ss>>a>>b>>c)d[a][b]=d[b][a]=c;
		rep(k,N)rep(i,N)rep(j,N)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
		
		int m=C.size();
		rep(i,N)rep(j,m+1)rep(k,m+1)dp[i][j][k]=j>k?0:INF;
		rep(i,N)rep(j,m)dp[i][j][j]=d[i][C[j]];
		for(int s=2;s<=m;s++)rep(i,N)rep(l,m-s+1){
			int r=l+s-1;
			if(i==C[l]){
				dp[i][l][r]=dp[i][l+1][r]; continue;
			}
			dp[i][l][r]=dp[C[l]][l+1][r]+d[i][C[l]];
			for(int m=l;m<r;m++)rep(j,N)
				dp[i][l][r]=min(dp[i][l][r],d[i][j]+dp[j][l][m]+dp[j][m+1][r]);
		}
		return dp[0][0][m-1]>=INF?-1:dp[0][0][m-1];
	}
};