/* 参考:http://blog.csdn.net/racebug2010/article/details/6683963 第一道状态压缩DP state的二进制表示(如110011)表示状态第1,2,5,6的点已经被消灭 DP[state]表示为state状态时的最小距离和 DP[state]=min(DP[state],DP[state^(1<<i)^(1<<j)]+dis(p[i],p[j])+dis(my,p[i])) 其中i表示state的第i位(这一位必须为1) 所以只要枚举两个state为1的位i,j进行状态转移(纯粹这样会超时) 由于110011可以由状态000011,010001,010010,100001,100010,110000这些状态而来 但000011和110011转换成110011的实质是一样的(都是1,2配对 5,6配对) 状态可以由六个减少到000011,010001,010010 三个 所以不需要枚举i,j,只需固定i,枚举j就行了 */ #include<iostream> #include <stdlib.h> #include <algorithm> #include <stdio.h> #include<vector> #include<cmath>; using namespace std; typedef __int64 i64; const int M=1000000007; struct Point { double x,y; }my,p[22]; int n; double dp[1<<21]; double dis(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } bool cmp(Point a,Point b) { return dis(my,a)<dis(my,b); } //优化前*********************************************************************************** // double DP(int state) // { // if(dp[state]>=0)return dp[state]; // dp[state]=1<<30; // for(int i=0;i<n;i++) // { // if(state&(1<<i)) // { // for(int j=i+1;j<n;j++) // if(state&(1<<j)) // dp[state]=min(dp[state],DP(state^(1<<i)^(1<<j))+dis(p[i],p[j])+dis(my,p[i])); // } // } // if(dp[state]==(1<<30)) // dp[state]=0; // return dp[state]; // } //优化后*********************************************************************************** double DP(int state) { if(dp[state]>=0)return dp[state]; dp[state]=1<<30; int pos=-1; for(int i=0;i<n;i++) { if(state&(1<<i)) { if(pos==-1)pos=i; else { dp[state]=min(dp[state],DP(state^(1<<i)^(1<<pos))+dis(my,p[pos])+dis(p[pos],p[i])); } } } if(dp[state]==(1<<30)) dp[state]=0; return dp[state]; } int main() { int Case; scanf("%d",&Case); for(int k=1;k<=Case;k++) { scanf("%lf%lf",&my.x,&my.y); scanf("%d",&n); n=2*n; for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); sort(p,p+n,cmp); for(int i=0;i<(1<<n);i++) dp[i]=-1; printf("Case #%d: %.2lf\n",k,DP((1<<n)-1)); } return 0; }