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; }