【luogu】 P1433 吃奶酪

题目描述
房间里放着n块奶酪。一只小老鼠要把它们都吃掉,问至少要跑多少距离?老鼠一开始在(0,0)点处。

输入格式:
第一行一个数n (n<=15)
接下来每行2个实数,表示第i块奶酪的坐标。
两点之间的距离公式=sqrt((x1-x2) * (x1-x2)+(y1-y2) * (y1-y2))

输出格式:
一个数,表示要跑的最少距离,保留2位小数。

原题戳这里
深搜,记录上一个点和已经吃了多少块奶酪,再立一个flag,防止一块奶酪吃很多次
再就是剪枝,不剪枝会超时,如果距离已经大于了最小值,就不必继续进行计算了,然后轻松AC

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
double ds,minn=9999.0,dis[20][20],d[20][2];
int n,f[20];
void dfs(int l,int tot)
{
if(tot==n&&minn>ds)
{
minn=ds;
return ;
}
else if(tot==n)
return ;
for(int i=1;i<=n;i++)
{
if(f[i]==0)
{
f[i]=1;
ds+=dis[l][i];
if(ds<minn)
dfs(i,tot+1);
f[i]=0;
ds-=dis[l][i];
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>d[i][1]>>d[i][2];
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
dis[i][j]=sqrt((d[j][1]-d[i][1])*(d[j][1]-d[i][1])+(d[j][2]-d[i][2])*(d[j][2]-d[i][2]));
dfs(0,0);
printf("%.2lf",minn);
return 0;
}
上一篇:c++ 备忘


下一篇:数据挖掘学习笔记——kaggle 数据预处理