题目描述
维修工要给n个客户更换设备，为每个用户更换一个设备。维修工背包内最多装k个设备，如果背包里有设备可以直接前往下一个客户更换或回公司补充设备，没有则需要回公司取设备。这些客户有优先级，维修工需要按照优先级给客户更换设备，优先级level用数字表示，数字小的优先级高。维修工从公司出发，给n个客户更换设备，最后再返回公司。请计算维修工完成这项工作所需要经历的最短总距离是多少。维修工可以走斜线。
输入描述
第一行两个正整数 n, k(1 ≤ k ≤ n ≤ 2000)，表示客户数和维修工背包容量。
第二行两个正整数 x, y ，用空格分隔(1 ≤ x, y ≤ 10^6)，表示公司的坐标。
接下来 n 行每行三个正整数 x_i, y_i, level_i，用空格分隔，表示第 i 个客户的位置坐标 (x_i, y_i) 和优先级 level_i。
保证所有客户优先级不同，客户和公司坐标不会重叠。
输出描述
输出最短总距离，结果四舍五入并保留一位小数，例如: 9.0。
用例输入
3 2
1 1
3 1 1
1 2 2
3 2 3
输出
9.2
从 (1, 1) → (3, 1) → (1, 1) → (1, 2) → (3, 2) → (1, 1)
计算距离：
(1, 1)→(3, 1)= 2(3, 1)→(1, 1)= 2(1, 1)→(1, 2)= 1(1, 2)→(3, 2)= √5 ≈ 2.236
总距离：2 + 2 + 1 + √5 = 9.236，四舍五入后为 9.2。
解题思路
题目要求按照客户的优先级来安排维修顺序。因为客户优先级是通过数字表示的，数字越小优先级越高。首先需要根据 level 对客户进行排序。
如果背包里有修理工具，则有两种情况：
- 情况1：直接去下一个地方修理
- 情况2：先去公司补工具，再去修理
如果背包里没有工具，只能回公司补工具，再修理。（同情况2）
使用 记忆化搜索 来避免重复计算。使用 memo[i][j] 来表示“维修完第 i 个客户，并且背包中剩余 j 个设备时，维修工完成任务所需的最短距离。
代码
对于每一个客户 i，有两种选择：
- 直接前往下一个客户（如果背包中有足够的设备，即 j > 0）：从客户 i 前往客户 i+1，消耗的距离为 dis(data[i].x, data[i].y, data[i+1].x, data[i+1].y)。更新状态为 memo[i+1][j-1]。
- 返回公司补充设备：从客户 i 返回公司，消耗的距离为 dis(data[i].x, data[i].y, cx, cy)。从公司再次前往客户 i+1，消耗的距离为 dis(data[i+1].x, data[i+1].y, cx, cy)。更新状态为 memo[i+1][k-1]（因为补充了设备，背包重新装满，然后又消耗了1个）。
需要取这两种选择的最小值。
当处理到最后一个客户（i == n-1）时，只需要从客户返回公司，消耗的距离为 dis(data[i].x, data[i].y, cx, cy)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<set>
using namespace std;double dis(int x1, int y1, int x2, int y2) {// 计算两点间的欧几里得距离return (double)sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}struct customer {int x, y, level; // 客户的坐标和优先级bool operator < (const customer& other) const {return level < other.level; // 按照优先级排序}
};double memo[2001][2001] = { 0 };
int n, k; // n: 客户数, k: 背包容量
int cx, cy; // 公司坐标// 已经完成前i个顾客，背包里还有j个工具时最小距离
double dfs(vector<customer>& data, int i, int j) {if (memo[i][j] > 0) return memo[i][j];// 计算到公司距离double cur = dis(data[i].x, data[i].y, cx, cy);double& res = memo[i][j];res = INT32_MAX;if (i < n - 1) { // 非最后一个客户// 回公司补充装备，再去下一个地方维修 res = min(res, dfs(data, i + 1, k - 1) + cur + dis(data[i + 1].x, data[i + 1].y, cx, cy));if (j > 0) {// 有剩余工具 直接去维修res = min(res, dfs(data, i + 1, j - 1) + dis(data[i].x, data[i].y, data[i + 1].x, data[i + 1].y));}}// i为 n-1else {res = cur;}cout << i << " " << j << " " << res << endl;return res;
}int main()
{ios::sync_with_stdio(false); // 关闭与 C 的同步cin.tie(nullptr); // 解除 cin 与 cout 的绑定cin >> n >> k >> cx >> cy;vector<customer> data(n);for (int i = 0; i < n; i++) {cin >> data[i].x >> data[i].y >> data[i].level;}sort(data.begin(), data.end());cout << dfs(data, 0, k - 1)+dis(data[0].x, data[0].y,cx,cy) << endl;
}
调用 dfs 函数，从第一个客户开始（已经完成了客户0），背包中初始设备数量为 k-1。最终结果加上从第一个客户到公司的距离，作为总的最小行驶距离。