猫史档案馆

题目描述

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

输入格式

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

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

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

输出格式

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

输入输出样例 输入 #1<button class="copy-btn lfe-form-sz-middle" type="button" data-v-f3e1ca6a="" data-v-89a1e792="">复制</button>

4
1 1
1 -1
-1 1
-1 -1

输出 #1<button class="copy-btn lfe-form-sz-middle" type="button" data-v-f3e1ca6a="" data-v-89a1e792="">复制</button>

7.41

直接上代码！自己理解一下：

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int n,v[1001];//v数组——>标记是否到过此点 
double x[100];
double y[20];//(x,y)，坐标 
double dis[1001][1001];//dis[i][j]，点i到点j的距离（要预处理） 
double ans=999999999.0; //保证ans足够大 
void dfs(int step,int now,double length) //step 已经走过几个点 now 当前走到的点 
                                         //length 走到的当前路径长 
{
    if(length>ans)//剪枝（不然会超时） 当前路径已经比目前最优值的要长了，就不必继续搜
      return;     //索，直接返回上一层                                                
    if(step==n)//走完n个点 
      {
          ans=min(ans,length);  //更新最短路径值 
          return;
      }
    for(int i=1;i<=n;i++)  //枚举所有点 
      if(!v[i])   //没有走过 
        {
            v[i]=1;  //标记为走过 
            dfs(step+1,i,length+dis[now][i]);  //深搜下一层 
            v[i]=0;  //回溯  从刚才上一层退回，把标记过的点取消标记 
        }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>x[i]>>y[i];
    x[0]=0;y[0]=0;  //设起点为第0个点 
    for(int i=0;i<=n;i++)  //预处理两点间距离 
      for(int j=0;j<=n;j++)
        dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    dfs(0,0,0.0);  //已走过0个点  上一个点是第0个点  已走了长0.0的路径 
    printf("%.2f",ans);
    return 0;
}