吃奶酪

题目传送门

解题思路

我们可以设一个f[i][j]
i表示，当前在i点，j表示一个二进制，其中0表示没走过，1表示走过
f [ j ] [ i ] = m i n ( f [ j ] [ i ] , d o u b l e ( 1.0 ∗ f [ k ] [ i − ( 1 < < j − 1 ) ] ) + d o u b l e ( 1.0 ∗ d i s ( j , k ) ) ) ; / / 状 态 转 移 f[j][i]=min(f[j][i],double(1.0*f[k][i-(1<<j-1)])+double(1.0*dis(j,k)));//状态转移 f[j][i]=min(f[j][i],double(1.0∗f[k][i−(1<<j−1)])+double(1.0∗dis(j,k)));//状态转移
d i s 为 两 点 间 的 距 离 dis为两点间的距离 dis为两点间的距离

AC代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
double s=2147483647.0,x[20],y[20],f[20][1<<20];
double dis(int i,int j)//两点中的坐标
{
   
	return sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]));
}
int main()
{
   
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
	for(int i=1;i<=n;i++)//初值
	 for(int j=1;j<=(1<<n)-1;j++)
	  f[i][j]=2147483647.0;
	for(int i=1;i<=(1<<n)-1;i++)//dp
	 for(int j=1;j<=n;j++)
	  if(i&(1<<j-1))//特判
	  {
   
	  	if(i!=(1<<j-1))//特判
	  	{
   
	  	  for(int k=1;k<=n;k++)
	  	   if(!(j==k||!(i&(1<<k-1))))//特判
	  	    f[j][i]=min(f[j][i],double(1.0*f[k][i-(1<<j-1)])+double(1.0*dis(j,k)));//状态转移
	  	}
		else f[j][i]=0.0; //初值
	  }
	for(int i=1;i<=n;i++)//找最小
	 s=min(s,double(1.0*f[i][(1<<n)-1])+double(1.0*dis(i,0)));
	if(s==2147483647)printf("-1");
	else printf("%.2lf",s);
	return 0;
}

谢谢