/* 这题的状态用普通方法不好表示,可以用状态压缩后的一维数组来表示, d[i]表示当前配对状态为i时的最短距离和。其中i用2进制表示后第k位如果是0则代表 第k位同学已经组队,1代表第k位同学还未组队。 状态转移方程:d[a]=min(d[a],dp(a^(1<<i)^(1<<j))+distance(i,j)); ^是异或运算,1^0=1,0^0=0;1^1=0; dp(a^(1<<i)^(1<<j))表示当前状态去掉第i个同学和第j个同学剩下的最小距离和。 */ #include <stdio.h> #include <string.h> #include <math.h> #define maxn 70000 struct node { int x,y; }p[20]; int vis[maxn],n; double d[maxn]; double min(double a,double b) { if(a<b)return a; else return b; } double dp(int a) { double &res=d[a]; int &flag=vis[a]; if(flag) return res; if(a==0) {res=0;flag=1;return 0;} res=1000000000; for(int i=0;i<n;i++) { if(!(a&(1<<i)))continue; for(int j=i+1;j<n;j++) { if(!(a&(1<<j)))continue; double temp=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)); res=min(res,dp(a^(1<<i)^(1<<j))+temp); } } flag=1; return res; } int main() { int t=0; while(scanf("%d",&n)&&n!=0) { getchar(); n=n*2; for(int i=0;i<n;i++) scanf("%*s%d%d",&p[i].x,&p[i].y); memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); double res=dp((1<<n)-1); printf("Case %d: %.2lf\n",++t,res); } return 0; }