嗯？这题竟然是个绿题。
这个题真的不难，不要被他的难度吓到，我们只是不会计算2点之间的距离，他还给出了公式，这个就有点……
我们直接套公式去求出需要的值，然后普通的搜索就可以了。
这个题我用的深搜，因为广搜没什么意义。
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
struct z
{
double x,y;
}g[20];
using namespace std;
double s[20][20];
int n,bj[20];
double maxx=9999999.0;
int dfs(int bs,int xz,double jl)//3个参数分别是吃了几个奶酪，现在在第几个奶酪的位置和一共走了多远。
{
if(jl>=maxx)//现在比最远的一次都远了，再走会更远。
{
return maxx;
}
if(bs==n)//全都吃完了，比较一下哪个大，返回
{
maxx=min(maxx,jl);
return maxx;
}
for(int i=1;i<=n;i++)
{
if(bj[i]==0)//bj表示这个奶酪吃过没有
{
bj[i]=1;//现在吃过了
dfs(bs+1,i,jl+s[xz][i]);//下一层循环。
bj[i]=0;//这次吃它的情况全试过了，试试这次不吃。
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)//正常的输入
{
cin>>g[i].x>>g[i].y;
}
g[0].x=0;
g[0].y=0;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)//s[i][j]的意思是第i块奶酪到第j块奶酪的距离
{
s[i][j]=sqrt((g[i].x-g[j].x)*(g[i].x-g[j].x)+(g[i].y-g[j].y)*(g[i].y-g[j].y));//公式套上。
}
}
dfs(0,0,0.0);//开始搜索
printf("%.2f",maxx);//保留2位小数。%.2f
return 0;
}
这个题没什么可讲的，一个纯洁的深搜就可以解决了。