ACM 训练日志记录 · 思考 · 成长
提交 / 修改记录
廖夏 / 题目列表训练档案
导出

P1433　吃奶酪

来源：洛谷 ★ 1500

DP搜索DFS剪枝模拟退火状压DP超纲待做待复习
本题活力0.07按难度、完成结果与训练证据估算

算法如山行则将至

查看原题廖夏 的主页

题目描述

吃奶酪

题目描述

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

输入格式

第一行有一个整数，表示奶酪的数量 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行两个实数，第 $(i + 1)$ 行的实数分别表示第 $i$ 块奶酪的横纵坐标 $x_i, y_i$。

输出格式

输出一行一个实数，表示要跑的最少距离，保留 $2$ 位小数。

说明/提示

数据规模与约定

对于全部的测试点，保证 $1\leq n\leq 15$，$|x_i|, |y_i| \leq 200$，小数点后最多有 $3$ 位数字。

提示

对于两个点 $(x_1,y_1)$，$(x_2, y_2)$，两点之间的距离公式为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。

$2022.7.13$：新增加一组 $\text{Hack}$ 数据。

样例 1

输入：

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

输出：

7.41

代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<vector>
using namespace std;
const int MAXN = 25;
struct coord{
    double x,y;
};
coord a[MAXN];
int n;
bool vis[MAXN];
double ans = 1e9;
double dis[MAXN][MAXN];
vector<int> order[MAXN];
void dfs(int index, double distance, int cnt){
    if (distance >= ans) return;
    if (cnt == n){
        ans = min(ans, distance);
        return;
    }
    for (int i : order[index]){
        if (!vis[i]){
            vis[i] = 1;
            dfs(i, distance + dis[index][i], cnt + 1);
            vis[i] = 0;
        }
    }
} // O(n!) 及其恐怖
double greedy(){
    bool used[MAXN] = {};
    int now = 0;
    double res = 0;

    for (int k = 1; k <= n; k++){
        int nxt = -1;

        for (int i = 1; i <= n; i++){
            if (!used[i] && 
                (nxt == -1 || dis[now][i] < dis[now][nxt])){
                nxt = i;
            }
        }

        used[nxt] = true;
        res += dis[now][nxt];
        now = nxt;
    }

    return res;
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
    // dis 预处理
    for (int i = 0; i <= n; i++){
        for (int j = 0; j <= n; j++){
            if (i == j) continue;
            dis[i][j] = hypot(a[i].x-a[j].x,a[i].y-a[j].y);
        }
    }
    // order 预处理
    for (int i = 0; i <= n; i++){
        for (int j = 1; j <= n; j++)
            if (i != j){
                order[i].push_back(j);
        }
        sort(order[i].begin(), order[i].end(), [i](int x, int y){
            return dis[i][x] < dis[i][y];
        });
    }
    double ans_tmp = 0;
    ans = greedy();
    dfs(0, 0, 0); // a[0].x = a[0].y = 0
    cout << fixed << setprecision(2) << ans;
    return 0;
}