RT

Subtask#0 Wa #5

Subtask#1 Wa #12 #13

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
struct Node
{
	double x,y;
}node[20];
double dis[20][20],f[20][40000],ans;
int n;

double distance(int x,int y)
{
	return sqrt(1.0*(node[x].x-node[y].x)*(node[x].x-node[y].x)+1.0*(node[x].y-node[y].y)*(node[x].y-node[y].y));
}

int main()
{
	memset(f,127,sizeof(f));
	ans=f[0][0];
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lf%lf",&node[i].x,&node[i].y);
	for(int i=0;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			dis[j][i]=dis[i][j]=distance(i,j);
	for(int i=1;i<=n;i++)
		f[i][1<<(i-1)]=dis[0][i];
	for(int k=1;k<(1<<n);k++)
		for(int i=1;i<=n;i++)
		{
			if(k&(1<<(i-1))==0)
				continue;
			for(int j=1;j<=n;j++)
			{
				if(i==j)
					continue;
				if(k&(1<<(j-1))==0)
					continue;
				f[i][k]=min(f[i][k],f[j][k-(1<<(i-1))]+dis[j][i]);
			}
		}
	for(int i=1;i<=n;i++)
		ans=min(ans,f[i][(1<<n)-1]);
	printf("%.2lf\n",ans);
	system("pause");
	return 0;
}