记录编号	592862	评测结果	AAAAAAAAAA
题目名称	线型网络	最终得分	100
用户昵称	qyd	是否通过	通过
代码语言	C++	运行时间	1.056 s
提交时间	2024-08-02 17:41:00	内存使用	27.13 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn=20;
const double INF=0x3f3f3f3f;
#define sqr(x) (x)*(x)
int n;
double ans,x[maxn],y[maxn],dist[maxn][maxn];
double f[1<<maxn][maxn];
void prework(){
	cin>>n;
	ans=INF;
	for(int i=0;i<n;i++)
	  cin>>x[i]>>y[i];
	for(int i=0;i<n;i++)
	  for(int j=0;j<n;j++)
	    dist[i][j]=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
	return ;
}
void dp(){
	int top=(1<<n);
	for(int i=0;i<top;i++)
	  for(int j=0;j<n;j++)
	    f[i][j]=INF;
	for(int i=0;i<n;i++)
	  f[1<<i][i]=0;
	for(int i=1;i<top;i++){
		for(int j=0;j<n;j++){
			if(i&(1<<j)){
				for(int k=0;k<n;k++){
					if(!(i&(1<<k))){
						f[i|1<<k][k]=min(f[i|1<<k][k],f[i][j]+dist[j][k]);
					}
				}
			}
		}
	}
	for(int i=0;i<n;i++)
	  ans=min(ans,f[top-1][i]);
}
int main()
{
	freopen("linec.in","r",stdin);
	freopen("linec.out","w",stdout);
	prework();
	dp();
	cout<<setprecision(2)<<fixed<<ans<<endl;
	return 0;
}