#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int n;//奶酪数
double a[16][3],f[16][16],ans=1<<30;//开double!a存储的是奶酪的数据,f是预处理每两个奶酪之间,ans则要取1个比较大的数
bool used[16];//标记是否吃过
void dfs(int num,int step,double sum)//num表示上一次吃了哪个奶酪,step表示现在要吃第几个,sum为距离和
{
if(sum>ans)//如果当前距离和大于答案了
return;//剪枝
if(step==n+1)//到达递归出口
{
ans=min(ans,sum);//答案为当前答案与新答案中的较小值
return;//return没有什么好解释的
}
for(int i=1;i<=n;i++)
if(!used[i])//如果没有吃过就吃这一块
{
used[i]=true;//标记为已吃过
sum+=f[num][i];//距离和加上这次的距离
dfs(i,step+1,sum);//递归
used[i]=false;//恢复标记
sum-=f[num][i];//恢复距离和
}
}
int main()
{
cin>>n;//输入奶酪数
a[0][1]=a[0][2]=0;//存储起点的数据
for(int i=1;i<=n;i++)
{
cin>>a[i][1]>>a[i][2];//输入每个奶酪的数据
for(int j=0;j<i;j++)
f[i][j]=f[j][i]=sqrt(abs(a[i][1]-a[j][1])*abs(a[i][1]-a[j][1])+abs(a[i][2]-a[j][2])*abs(a[i][2]-a[j][2]));//边读入边预处理
}
dfs(0,1,0);//从起点开始搜
cout<<fixed<<setprecision(2)<<ans;//保留两位小数输出
return 0;//结束
}
P1433 吃奶酪
2019-05-10