POJ 1695 Magazine Delivery

問題

N箇所の地点に3台の車を使って雑誌を配達する。
N箇所地点のそれぞれの間の距離は与えられている。


車の動かし方には以下のような制限がある。

  • 一度に同時に動かせる車は一台だけ
  • L[i]番目の地点に訪れるにはL[i-1]番目の地点を訪れなければならない

制約条件

N≦30

方針

dp[i][j][k]を車1がi,車2がj,車3がkにいる状態にかかる最短の時間とするようなDPができる。
ただしi≧j≧kとしてよい。


車がもと来た道を戻ったり、まだ訪れてない地点が近道になるのでそこを通ったりするとWAになる、しかもそれが問題文にはっきり書かれていないという悪問。


車が配達しさえすれば良いという場合には、地点間の距離を最初にワーシャルフロイドしておけばいい。

ソースコード

int n, d[30][30];
int dp[30][30][30];

int main()
{
	int M; scanf("%d",&M);
	while(M--){
		scanf("%d",&n);
		rep(i,n)rep(j,n)rep(k,n)dp[i][j][k]=(int)1e9;
		rep(i,n)rep(j,n-i-1){
			scanf("%d",d[i+1+j]+i);
			d[i][i+1+j]=d[i+1+j][i];
		}
		//rep(k,n)rep(i,n)rep(j,n)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
		
		dp[0][0][0]=0;
		rep(i,n-1)rep(j,i+1)rep(k,j+1){
			dp[i+1][i][j]=min(dp[i+1][i][j],dp[i][j][k]+d[k][i+1]);
			dp[i+1][i][k]=min(dp[i+1][i][k],dp[i][j][k]+d[j][i+1]);
			dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]+d[i][i+1]);
		}
		
		int ans=(int)1e9;
		rep(i,n)rep(j,n)ans=min(ans,dp[n-1][i][j]);
		printf("%d\n",ans);
	}
	return 0;
}