10911:Forming Quiz Teams

問題文
http://uva.onlinejudge.org/external/109/10911.html

n*2個の点の座標が与えられる。これらの点をペアにしたときの2点間の距離の和の最小値を求めよ。

ビットDPした。
dp[使った点の集合]:=距離の和の最小値

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cmath>

#define x first
#define y second
#define INF (1<<29)

using namespace std;

typedef pair<double,double> P;

vector<P>p;

double dist(int u,int v){return sqrt(pow(p[v].x-p[u].x,2)+pow(p[v].y-p[u].y,2));}

int main(void){
	
	int n,Case=1;
	while(cin >> n,n){
		n*=2;
		string s;
		p.resize(n);
		for(int i=0;i<n;i++)cin >> s >> p[i].x >> p[i].y;
		
		double dp[(1<<17)];
		fill(dp,dp+(1<<17),INF);
		dp[0]=0;
		
		for(int S=0;S<(1<<n);S++){
			for(int u=0;u<n;u++){
				for(int v=0;v<n;v++){
					int next=S;
					if(u==v || (next>>u)&1 || (next>>v)&1)continue;
					next|=(1<<u);
					next|=(1<<v);
					dp[next]=min(dp[next],dp[S]+dist(u,v));
				}
			}
		}
		printf("Case %d: %.2f\n",Case++,dp[(1<<n)-1]);
	}
	
	return 0;
}