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

P1433　吃奶酪

来源：洛谷 ★ 1500

DP搜索DFS剪枝模拟退火状压DP仍在学习待复习
本题活力0.21本次有不同于此前记录的心得，计入额外复盘活力

算法如山行则将至

查看原题廖夏 的主页

题目描述

吃奶酪

题目描述

房间里放着 $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

代码

/*
Time: 2026-10-14
Author: only_matthew
Satement: 这是深入浅出基础篇基础算法部分的最后一道题. 五年已逝，终于要结束第一段旅程了. 
IDE: Dev-C++ 5.11 (For commemorate the 'HelloWrold!' in 7 2019) 
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
using namespace std;
const int MAXN = 20;
int n;
double dp[1<<15][16];
struct Coord{
	double x, y;
}; 
Coord a[MAXN];
double dis[MAXN][MAXN];
int main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
	for (int i = 0; i <= n; i++){ // 从0开始遍历，从而保证起点不出错 
		for (int j = 0; j <= n; j++){
			double dx = a[i].x - a[j].x;
			double dy = a[i].y - a[j].y;
			dis[i][j] = sqrt(dx * dx + dy * dy);
		}
	}
//	memset(dp, 1e18, sizeof(dp));
	for (int mask = 1; mask < 1<<n; mask++)
		for (int i = 1; i <= n; i++)
			dp[mask][i] = 1e18; 
	for (int i = 1; i <= n; i++)
		dp[1 << (i-1)][i] = dis[0][i];
	for (int mask = 1; mask < (1 << n); mask++){
		for (int i = 1; i <= n; i++){// 枚举已选择的点 
			if (!(mask & 1 << (i-1))) continue; // 未选择 
			if (dp[mask][i] == 1e18) continue;
			for (int j = 1; j <= n; j++){ // 枚举下一个点 
				if (mask & (1 << (j-1))) continue; // 已选择 
				int newmask = mask | (1 << (j - 1));
				dp[newmask][j] = min(dp[newmask][j], dp[mask][i] + dis[i][j]); 
			} 
		} 
	}  
	double ans = 1e18;
	for (int i = 1; i <= n; i++) ans = min(ans,dp[(1<<n) - 1][i]); 
	cout << fixed << setprecision(2) << ans;
	return 0; 
}