吃奶酪 洛谷 p1433

题目描述

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

输入输出格式

输入格式：

第一行一个数n (n<=15)

接下来每行2个实数，表示第i块奶酪的坐标。

两点之间的距离公式=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))

输出格式：

一个数，表示要跑的最少距离，保留2位小数。

输入输出样例

输入样例#1：

4

1 1

1 -1

-1 1

-1 -1

输出样例#1：

7.41

这道题数据不大，但增加一个最优性剪枝还是是好的，通过三个参数进行搜索并更新最小距离并输出即可，注意点和距离要用double存.

上代码：

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 using namespace std;

 int n;

 double minl=(<<)-;

 bool vis[];

 struct node{

     double x,y;

 }a[];

 void dfs(int nowp,double nowl,int step){//（当前所在的点，当前已经走的距离，当前将处理第几个点）

     if(step==n+&&nowl<minl){//如果step==n+1说明已经有n个点处理完了，即已经遍历完，更新最小距离

         minl=nowl;

     }

     if(nowl>minl){//最优性剪枝

         return;

     }

     for(int i=;i<=n;i++){

         if(vis[i]==){

             vis[i]=;

             dfs(i,nowl+sqrt((a[nowp].x-a[i].x)*(a[nowp].x-a[i].x)+(a[nowp].y-a[i].y)*(a[nowp].y-a[i].y)),step+);

             vis[i]=;

         }

     }

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++)

         scanf("%lf%lf",&a[i].y,&a[i].x);

     dfs(,,);

     printf("%.2lf",minl);

     return ;

 }