A6203 | Traveling Salesman among Aerial Cities
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
在三维空间中有 $N$ 个城市，编号为 $1$ 到 $N$。城市 $i$ 的坐标为 $(X_i, Y_i, Z_i)$。
从坐标为 $(a, b, c)$ 的城市移动到 $(p, q, r)$ 的城市时，所需的花费为 $|p-a| + |q-b| + \max(0, r-c)$。
请你求出从城市 $1$ 出发，经过所有城市至少一次并最终回到城市 $1$ 的最小总花费。
从坐标为 $(a, b, c)$ 的城市移动到 $(p, q, r)$ 的城市时，所需的花费为 $|p-a| + |q-b| + \max(0, r-c)$。
请你求出从城市 $1$ 出发，经过所有城市至少一次并最终回到城市 $1$ 的最小总花费。
输入格式
输入以以下格式从标准输入读入。
$N$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_N$ $Y_N$ $Z_N$
输出格式
输出从城市 $1$ 出发，经过所有城市至少一次并最终回到城市 $1$ 的最小总花费。
输入输出样例
输入 #1
2 0 0 0 1 2 3
输出 #1
9
输入 #2
3 0 0 0 1 1 1 -1 -1 -1
输出 #2
10
输入 #3
17 14142 13562 373095 -17320 508075 68877 223606 -79774 9979 -24494 -89742 783178 26457 513110 -64591 -282842 7124 -74619 31622 -77660 -168379 -33166 -24790 -3554 346410 16151 37755 -36055 51275 463989 37416 -573867 73941 -3872 -983346 207417 412310 56256 -17661 -42426 40687 -119285 43588 -989435 -40674 -447213 -59549 -99579 45825 7569 45584
输出 #3
6519344
限制条件
- $2 \leq N \leq 17$
- $-10^6 \leq X_i, Y_i, Z_i \leq 10^6$
- 不会有多个城市位于相同的坐标
- 所有输入均为整数
样例解释 1
从城市 $1$ 到城市 $2$ 的花费为 $|1-0| + |2-0| + \max(0, 3-0) = 6$。
从城市 $2$ 回到城市 $1$ 的花费为 $|0-1| + |0-2| + \max(0, 0-3) = 3$。
因此总花费为 $9$。
样例解释 2
例如按城市 $1$、$2$、$1$、$3$、$1$ 的顺序移动，总花费为 $10$。途中可以多次回到城市 $1$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？