记录编号	186810	评测结果	AAAAAAAAAA
题目名称	线型网络	最终得分	100
用户昵称	赵日天	是否通过	通过
代码语言	C++	运行时间	1.112 s
提交时间	2015-09-15 15:25:39	内存使用	172.53 MiB

#include <cmath>
#include <cstdio>
//----------------------------------------------------
inline double Min(double num1,double num2) { return num1<num2?num1:num2; }
inline double sqr(double num1) { return num1*num1; }
//----------------------------------------------------
int  n;
int  i,j,k;
int num1[1050000];

double x[30],y[30];
double dis[30][30];

double dai,cache=99999999;
double ans[1050000][21];
//----------------------------------------------------
int  main( )
{
	freopen( "linec.in"  , "r" , stdin  );
	freopen( "linec.out" , "w" , stdout );
	scanf("%d",&n);
	for (i=1; i<=n; i++)
	{
		scanf("%lf%lf",&x[i],&y[i]);
		for (j=1; j<i; j++)
		{
			dis[i][j]=
			dis[j][i]=sqrt( sqr(x[i]-x[j]) + sqr(y[i]-y[j]) );
		}
	}
	//-- s1
	for (i=0; i<=n; i++) num1[1<<i]=i+1;
	//-- s2
	for (i=1; i< 1<<n; i++) if (!num1[i])
	for (j=i; j; j-=j&-j) //j枚举状态i的每一个1，标记当前终点
	{
		ans[i][num1[j&-j]]=99999999;
		//更新目标: ans[i][num1[j&-j]]   
		for (k=i-(j&-j); k; k-=(k&-k))  // 枚举上一个位置 
		if (ans[i][num1[j&-j]] > ans[i-(j&-j)][num1[k&-k]] + dis[num1[j&-j]][num1[k&-k]])
			ans[i][num1[j&-j]] = ans[i-(j&-j)][num1[k&-k]] + dis[num1[j&-j]][num1[k&-k]];
		//更新来源：ans[i-j&-j][num1[k&-k]]
	}	
	//-- s3
	for (i=1; i<=n; i++)
		cache=Min(cache,ans[(1<<n)-1][i]);
	printf("%.2f",cache);
}