题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3920
#include <algorithm>
#include <iostream>
#include<cmath>
#include<cstring>
#include<stdio.h>
#define maxn 30
#define MAX 100000000
#define db double
using namespace std;
int sx,sy;
int n;
struct node{int x,y;node(double xx=0,double yy=0){x=xx;y=yy;}
};
/*
题目大意：给定2*n个点坐标，
要求每次设计可以打击到两个点，（是一条路径），
求最小代价。首先分析贪心性质：如果只有两个点如何选择？
两点间的连线距离肯定要算上，那么选取的最佳情况
就是两点到原点的最短距离，所以预处理先按到原点距离对2n个点排序。
其次分析数据，数据只有10容易想到状态压缩的情况。下面就是动态规划的基本操作了，对一个状态从没选过的点集中遍历两个点的选取，
就可以递推到下一个状态了。
等等！为什么正推超时了？参考网上的说法结合自己的理解，应该是选择顺序的问题，正推会产生很多选择顺序不同
的无关状态，而逆推属于深搜，所以对于一个情况会一次性判到底，所以不会有这种情况。
当然，我想也有测试数据本身的特殊分布在里面吧
*/
node seq[maxn];
double c[maxn];
double vis[1<<21];
double dis[maxn][maxn];
double dist(node &n1,node& n2){int a=n1.x-n2.x;int b=n1.y-n2.y;return sqrt(1.0*a*a+1.0*b*b);
}
bool cmp(node& p,node& q){node tmp=node(sx,sy);return dist(p,tmp)<dist(q,tmp);
}
double compute(node& n1,node& n2){double ans=dist(n1,n2);node tmp=node(sx,sy);if( cmp(n1,n2) ) ans+=dist(n1,tmp);else ans+=dist(n2,tmp);//cout<ans<<endl;return ans;
}double memdfs(int sta){if(vis[sta]>=0) return vis[sta];if(sta== 0) return 0.0;double ans=MAX;int i=0;while( (sta&(1<<i))==0 ) i++;for(int j=i+1;j<n;j++){if((1<<j)&sta)ans=min(ans,memdfs(sta-(1<<j)-(1<<i)) + compute(seq[i],seq[j]) );}return vis[sta]=ans;
}int main(){int t;cin>>t;for(int ca=1;ca<=t;ca++){scanf("%d%d",&sx,&sy);scanf("%d",&n); n*=2;for(int i=0;i<n;i++) scanf("%d%d",&seq[i].x,&seq[i].y);for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)dis[i][j]=compute(seq[i],seq[j]);sort(seq,seq+n,cmp);memset(vis,-1,sizeof(vis));printf("Case #%d: %.2f\n",ca,memdfs((1<<n)-1) );}return 0;
}