题目链接：https://www.luogu.org/problemnew/show/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 解题分析：
此题若用dfs来做的话，需要剪枝，不然必定超时，常规的有两种剪枝方法：
1.当搜索的距离大于此时保存的最小总距离的时候，这条dfs路线必然不符合要求，直接return，这个很关键。
2.搜索的时候不断求两点之间的距离非常耗时，所以我们可以在一开始就打好表，用dis[][]二维数组储存每两点之间的距离，然后后面搜索的时候直接调用就好了。（不过下面我的代码没有用到这个剪枝，也勉强AC了）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int n, res;double ans;
int vis[];
struct node
{
double x, y;
};
node arr[]; double dis(node a, node b)
{
double sum = ;
sum += sqrt((a.x - b.x)*(a.x - b.x)*1.0 + (a.y - b.y)*(a.y - b.y)*1.0);
return sum;
} void dfs(int ord,double distance) //当前点的序号 、总距离
{
if (distance >= ans)return; //如果距离大于等于现在的最小值，该dfs路线直接放弃，这个剪枝很重要
if (res == n&&distance<ans)
{
ans = distance; //更新最小值
}
for (int i = ; i <= n; i++)
{
if (!vis[i])
{
res++; vis[i] = ; //选这个点
dfs(i, distance + dis(arr[ord], arr[i]));
res--; vis[i] = ; //清空当前选择
}
}
} int main()
{
scanf("%d", &n);
for (int i = ; i <= n; i++)
{
scanf("%lf %lf", &arr[i].x, &arr[i].y);
}
arr[].x = ,arr[].y=;
ans = INF; res = ;
dfs(,);
printf("%.2lf\n", ans);
return ;
}
用了二维数组记录两点之间距离代码
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f
int n,cur;
double ans; struct node
{
double x, y;
};
node arr[];
int vis[];
double map[][]; double dis(int i, int j)
{
return sqrt((arr[i].x-arr[j].x)*(arr[i].x - arr[j].x)+(arr[i].y-arr[j].y)*(arr[i].y - arr[j].y));
} void dfs(int ord,double sum)
{
if (sum >= ans)return;
if (cur == n)
{
ans = min(sum, ans);
}
else
{
for (int i = ; i <= n; i++)
{
if (!vis[i])
{
vis[i] = ; cur++;
dfs(i,sum +map[ord][i]);
vis[i] = ; cur--;
}
}
}
} int main()
{
cin >> n;
arr[].x = , arr[].y = ;
for (int i = ; i <= n; i++)
{
scanf("%lf %lf", &arr[i].x, &arr[i].y);
}
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
map[i][j] = dis(i, j); //开一个二维数组来记录任意两个点之间的距离，省的以后多次求（虽然对这道题来说并没有优化多少）
} //注意此时i-j的距离，还要记录j-i的距离，虽然这两个距离的值是一样的，但是遍历的时候，i有可能在j的前面，也有可能在j的后面，所以map[i][j]和map[j][i]都要记录
}
memset(vis, , sizeof(vis));
ans = INF,cur=;
dfs(,);
printf("%.2lf\n", ans);
return ;
}
2018-05-31