题目描述
房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0) 点处。
输入格式
第一行有一个整数，表示奶酪的数量 nn。
第 2 到第 (n+1) 行，每行两个实数，第 (i+1)(i+1) 行的实数分别表示第 ii 块奶酪的横纵坐标 xi,yi。
输出格式
输出一行一个实数，表示要跑的最少距离，保留 2 位小数。
输入输出样例
输入 #1
4
1 1
1 -1
-1 1
-1 -1输出 #1
7.41说明/提示
数据规模与约定
对于全部的测试点，保证 1≤n≤15，∣xi∣,∣yi∣≤200，小数点后最多有 3 位数字。
提示
对于两个点 (x1,y1)，(x2,y2)，两点之间的距离公式为 (x1−x2)^2+(y1−y2)^2。
2022.7.13：新增加一组 HackHack 数据。
运用的相关知识以及自我理解
1.dfs。
2.状态压缩。
这个第一次看见也不要觉得这有多难就是一个二进制来表示一种状态。将输入的点从0开始编号当这个点被走过就将其对应的数位写为1，再将其转化为十进制来表示现在已经走过的点。
3.剪枝。
之前提到了一个状态当状态的由来是不为一的（相同的两个点可能先走或者后走，但是走完两个点后的状态是相同的那就意味着后面可能是会进行相同的操作），所以我们需要将这种情况减去，我们再仔细想一下如果我们到达该状态所走的路程小于已经存储的路程那后面的路程不就一定会大于已经储存的答案吗。
#include<stdio.h>
#include<math.h>
int n;
double ans,f[16][35000];
struct point
{
double x,y;
int visit;
int num;
}ps[16];
double dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void dfs(point p,int step,int mark,double s)
{
if(step==n)
{
if(ans>s)ans=s;
return ;
}
for(int i=0;i<n;i++)
{
if(ps[i].visit==1)continue;
int tmp=mark+(1<<i);
if(f[i][tmp] == 0 || f[i][tmp] > f[p.num][mark] + dis(ps[i],p))
{
f[i][tmp] = f[p.num][mark] + dis(ps[i],p);
ps[i].visit=1;
dfs(ps[i],step + 1,tmp,s + dis(ps[i],p));
ps[i].visit=0;
}
}
}
int main()
{
scanf("%d",&n);
ans=999999999;
for(int i=0;i<n;i++)
{
scanf("%lf %lf",&ps[i].x,&ps[i].y);
ps[i].visit=0;
ps[i].num=i;
}
point p={0,0,1,0};
dfs(p,0,0,0);
printf("%.2lf",ans);
return 0;
}