T15:Traveling Salesm

解题思路（状态压缩 TSP）

要求从城市 1 出发，至少经过所有城市一次并回到城市 1 的最小花费。因为花费都是非负的，重复走路只会更大，所以最优解一定可以看作：每个城市恰好访问一次（最后回到 1），也就是 TSP 问题。

N ≤ 17，可以用 状态压缩 DP。

---

1）预处理两两移动代价

城市 i 到城市 j 的花费：

• abs(Xj - Xi) + abs(Yj - Yi) + max(0, Zj - Zi)

先把 cost[i][j] 预处理出来，后面 DP 直接查表。

---

2）DP 定义

用二进制 mask 表示已经访问过的城市集合（包含城市 0 代表城市 1）。

定义：

• dp[mask][i]：从城市 1 出发，访问了 mask 里的所有城市，并且当前停在 i 的最小花费

  这里 i 用 0..N-1 表示城市 1..N。

初始化：

• dp[1<<0][0] = 0（只在城市 1）

转移：

• 从 dp[mask][i] 走到一个没访问过的 j：
  • dp[mask | (1<<j)][j] = min(dp[mask | (1<<j)][j], dp[mask][i] + cost[i][j])

答案：

• 最后要回到城市 1：
  • ans = min(dp[full][i] + cost[i][0])，其中 full = (1<<N) - 1

复杂度大约 O(N^2 * 2^N)，N=17 可以通过。

---

C++ 代码

#include <bits/stdc++.h>                     // 引入常用标准库头文件（竞赛常用）
using namespace std;                         // 使用 std 命名空间

const long long INF = (1LL<<62);             // 定义一个足够大的数，表示无穷大

static long long X[20], Y[20], Z[20];        // 存每个城市的三维坐标（N<=17，开到20足够）
static long long cost[20][20];               // cost[i][j] 表示从城市 i 到城市 j 的花费
static long long dp[1<<17][17];              // dp[mask][i]：访问集合mask，最后在i的最小花费

int main() {                                 // 主函数入口
    ios::sync_with_stdio(false);             // 加速输入输出（关闭同步）
    cin.tie(nullptr);                        // 加速输入输出（解除 cin 与 cout 绑定）

    int N;                                   // 城市数量
    cin >> N;                                // 读入 N
    for (int i = 0; i < N; i++) {            // 循环读入每个城市坐标
        cin >> X[i] >> Y[i] >> Z[i];         // 读入第 i 个城市的 (X,Y,Z)
    }

    for (int i = 0; i < N; i++) {            // 枚举起点城市 i
        for (int j = 0; j < N; j++) {        // 枚举终点城市 j
            long long dx = llabs(X[j] - X[i]); // 计算 x 方向距离的绝对值
            long long dy = llabs(Y[j] - Y[i]); // 计算 y 方向距离的绝对值
            long long dz = Z[j] - Z[i];        // 计算 z 方向的上升量（可能为负）
            if (dz < 0) dz = 0;                // 只有上升才计费，下降不加费
            cost[i][j] = dx + dy + dz;         // 按题意得到从 i 到 j 的总花费
        }                                     // j 循环结束
    }                                         // i 循环结束

    int FULL = (1 << N) - 1;                 // FULL 表示所有城市都访问过的状态（全 1）

    for (int mask = 0; mask <= FULL; mask++) { // 枚举所有状态 mask
        for (int i = 0; i < N; i++) {          // 枚举最后停在的城市 i
            dp[mask][i] = INF;                 // 初始化为 INF（表示不可达或未更新）
        }                                      // i 循环结束
    }                                          // mask 循环结束

    dp[1][0] = 0;                             // 初始：只访问城市0(城市1)，花费为0，停在城市0

    for (int mask = 1; mask <= FULL; mask++) { // 枚举当前已访问的集合 mask
        for (int i = 0; i < N; i++) {          // 枚举当前所在城市 i
            if (!(mask & (1 << i))) continue;  // 如果 i 不在 mask 中，说明不可能停在 i，跳过
            long long cur = dp[mask][i];       // 取出当前状态的最小花费
            if (cur >= INF) continue;          // 如果当前状态不可达，跳过
            for (int j = 0; j < N; j++) {      // 枚举下一步要去的城市 j
                if (mask & (1 << j)) continue; // 如果 j 已经访问过，就不能再作为“新访问”转移
                int nmask = mask | (1 << j);   // 新状态：把 j 加入已访问集合
                dp[nmask][j] = min(dp[nmask][j], cur + cost[i][j]); // 更新到新状态的最小花费
            }                                   // j 循环结束
        }                                       // i 循环结束
    }                                           // mask 循环结束

    long long ans = INF;                      // 最终答案初始化为 INF
    for (int i = 0; i < N; i++) {             // 枚举最后停在的城市 i（已经访问完所有城市）
        ans = min(ans, dp[FULL][i] + cost[i][0]); // 从 i 回到起点0，取最小总花费
    }                                         // i 循环结束

    cout << ans << endl;                      // 输出答案并换行
    return 0;                                 // 程序结束
}                                             // main 结束