记录编号	308019	评测结果	AAAAAAAAAA
题目名称	线型网络	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.406 s
提交时间	2016-09-16 18:05:35	内存使用	160.29 MiB

#include<cstdio>
#include<cmath>
using namespace std;
const int N=(1<<20);
typedef double db;
struct point{db x,y;}p[20];
int n,r,t[20];
db f[20][20];//f[i][j]表示从点i到点j的距离 
inline db sqr(double x){return x*x;}
inline db dis(int x,int y){
	return sqrt(sqr(p[x].x-p[y].x)+sqr(p[x].y-p[y].y));
}
db dp[20][N];//dp[j][i]表示走过的点的集合为i，最终到j的最短路 
inline db min(db x,db y){return x<y?x:y;} 
int main()
{
	freopen("linec.in","r",stdin);
	freopen("linec.out","w",stdout);
	for (int i=0;i<20;i++) t[i]=(1<<i);
	scanf("%d",&n);r=(1<<n);
	for (int i=0;i<n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	for (int i=0;i<n;i++)
	for (int j=0;j<n;j++)
		f[i][j]=dis(i,j);
	for (int i=0;i<n;i++)
	for (int j=0;j<r;j++)
		dp[i][j]=1e+9;
	for (int i=0;i<n;i++) dp[i][t[i]]=0;
	for (int j=1;j<r;j++)
	for (int i=0;i<n;i++)
	if (j&t[i]){
		for (int k=0;k<n;k++)
		if (!(j&t[k]))
			dp[k][j|t[k]]=min(dp[k][j|t[k]],dp[i][j]+f[i][k]);
	}
	db ans=1e+9;
	for (int i=0;i<n;i++)
		ans=min(ans,dp[i][r-1]);
	printf("%.2lf\n",ans);
	return 0;
}