69 lines
2.0 KiB
C++
69 lines
2.0 KiB
C++
#include<bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int INF = 0x3f3f3f3f;
|
||
|
||
const int N = 16; //对于全部的测试点，保证 1<=n<=15，
|
||
int n; //一共多少个奶酪
|
||
double res = INF; //记录最短路径长度,也就是最终的答案
|
||
double dis[N][N]; //dis[i][j]记录第i个点到第j的点的距离.这个是预处理的二维数组，防止重复计算,预处理是搜索优化的重要手段
|
||
bool vis[N]; //记录i奶酪在当前的路径探索中是否已经尝试过(可以重复使用噢~)
|
||
|
||
//坐标
|
||
struct Point {
|
||
double x, y;
|
||
} a[N];
|
||
|
||
/**
|
||
*
|
||
* @param pos 当前走的是第几个奶酪
|
||
* @param num 已吃掉的奶酪个数
|
||
* @param dis 当前距离的值
|
||
*/
|
||
void dfs(int pos, int num, double len) {
|
||
//剪一下枝
|
||
if (len >= res) return;
|
||
|
||
//前n个都吃完了，可以进行路线长短对比了
|
||
if (num == n) {
|
||
res = min(len, res);
|
||
return;
|
||
}
|
||
//从pos出发，向1~n个奶酪进军，去吃~
|
||
for (int i = 1; i <= n; i++) {
|
||
//回溯算法的套路，如果在本次寻找过程中，没有走过这个节点
|
||
if (!vis[i]) {
|
||
//标识使用过了
|
||
vis[i] = true;
|
||
//再走一步
|
||
dfs(i, num + 1, len + dis[pos][i]);
|
||
//反向标识
|
||
vis[i] = false;
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
//老鼠的原始位置
|
||
a[0].x = 0, a[0].y = 0;
|
||
|
||
//读入奶酪的坐标
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
|
||
|
||
//预处理(dfs能进行预处理的尽量预处理)
|
||
for (int i = 0; i < n; i++)
|
||
for (int j = i + 1; j <= n; j++) {
|
||
double x1 = a[i].x, y1 = a[i].y, x2 = a[j].x, y2 = a[j].y;
|
||
dis[j][i] = dis[i][j] = sqrt(abs((x1 - x2) * (x1 - x2)) + abs((y1 - y2) * (y1 - y2)));
|
||
}
|
||
//开始暴搜
|
||
dfs(0, 0, 0);
|
||
|
||
//输出结果
|
||
printf("%.2f", res);
|
||
return 0;
|
||
}
|
||
|
||
|