yukicoder : No.134 走れ！サブロー君

小数にやられた。
http://yukicoder.me/problems/273

問題

碁盤目状の道路がある町がある。
酒屋の座標(X[0],Y[0])と、N箇所の配達先の座標(X[i],Y[i])および配達物の重さW[i]が与えられる。

酒屋で全配達物をトラックに積み、N箇所の配達先に配達物を渡し、酒屋に戻ってきたい。

配達に置いては以下の通り時間がかかる。

• トラックはY軸方向およびX軸方向に沿ってのみ移動できる。
• トラックに積み荷の総重量がWの時、１移動するのにかかる時間は(W+100)/120となる。
• 配達先で配達物を渡すのにはW[i]の時間がかかる。

全配達物の配達後、酒屋に戻るまでの最小時間を答えよ。

解法

N箇所の配達先と酒屋を含めた(N+1)地点でBitDPすればよい。
[最後の訪問先][訪問済みの配達先のbitmask]を状態として持ち、最小時間を更新していく。

int N;
int X[100],Y[100];
double W[100],TW;
double dp[15][1<<15];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X[0]>>Y[0];
	cin>>N;
	FOR(i,N) cin>>X[i+1]>>Y[i+1]>>W[i+1], TW+=W[i+1];
	N++;
	FOR(i,N) FOR(j,1<<N) dp[i][j]=1e15;
	dp[0][0]=0;
	
	for(int mask=0;mask<1<<N;mask++) {
		FOR(i,N) if(dp[i][mask]<1e15) {
			double lw=TW;
			FOR(j,N) if(mask&(1<<j)) lw-=W[j];
			FOR(j,N) if((mask&(1<<j))==0) {
				int lo=abs(X[j]-X[i])+abs(Y[j]-Y[i]);
				dp[j][mask | (1<<j)] = min(dp[j][mask | (1<<j)], dp[i][mask] + lo*(lw+100.0)/120 + W[j]);
			}
		}
	}
	_P("%.12lf\n",dp[0][(1<<N)-1]);
}

まとめ

重さが小数なのにやられた。