AtCoder ABC #180 : E - Traveling Salesman among Aerial Cities

時間通り出ておけばよかったね。
https://atcoder.jp/contests/abc180/tasks/abc180_e

問題

3次元座標上にN個の点があり、各座標が与えられる。
2点間を移動する際にかかるコストは、X・Y軸はマンハッタン距離で、Z軸は増加する方向に移動する場合その差分、減少するときは0である。
1番の点から初めて、全点を1回以上通って最初の点に戻る最小コストを求めよ。

解法

今回のコストの計算式では、2点間を移動する際に他の点を通ることで得することはない。
なのでBitDPの要領でO(N*2^N)かけて全パターン列挙すればよい。

int N;
int X[20],Y[20],Z[20];
ll dp[1<<17][17];

int dif(int a,int b) {
	return abs(X[a]-X[b])+abs(Y[a]-Y[b])+max(0,Z[b]-Z[a]);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i]>>Z[i];
	FOR(i,N) FOR(j,1<<N) dp[j][i]=1LL<<60;
	dp[1][0]=0;
	int mask;
	FOR(mask,1<<N) {
		FOR(x,N) if(mask&(1<<x)) {
			FOR(y,N) dp[mask|(1<<y)][y]=min(dp[mask|(1<<y)][y],dp[mask][x]+dif(x,y));
		}
	}
	
	cout<<dp[(1<<N)-1][0]<<endl;
	
}

まとめ

なんでこれEなんだろ。