如题

代码

#include<bits/stdc++.h>

using namespace std;

int n;
double dp[100001][21],a[21],b[21],ans=1e9;
bool v[21]={0};

double cd(int x,int y)
{
	return sqrt((a[x]-a[y])*(a[x]-a[y])+(b[x]-b[y])*(b[x]-b[y]));
}

void dfs(int t,int now,double s,int b)
{
	if (t==n)
	{
		ans=ans<s?ans:s;
		return;
	}
	if (s>ans)
		return;
	for(int i=1;i<=n;i++)
	{
		if (v[i]==0)
		{
			int p=b+(1<<(i-1));
			if (dp[p][i]!=0&&dp[p][i]<=s+cd(now,i))
				continue;
			v[i]==1;
			dp[p][i]=s+cd(now,i);
			dfs(t+1,i,dp[p][i],p);
			v[i]==0;
		}
	}
}

int main()
{
	int i;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	dfs(0,0,0,0);
	printf("%0.2lf",ans);
	return 0;
}

只有20分