AT_abc180_e [ABC180E] Traveling Salesman among Aerial Cities

题目描述

在三维空间中有 $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$ 的最小总花费。

输入格式

输入以以下格式从标准输入读入。

$N$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_N$ $Y_N$ $Z_N$

输出格式

输出从城市 $1$ 出发，经过所有城市至少一次并最终回到城市 $1$ 的最小总花费。

输入输出样例 #1

输入 #1

2
0 0 0
1 2 3

输出 #1

9

输入输出样例 #2

输入 #2

3
0 0 0
1 1 1
-1 -1 -1

输出 #2

10

输入输出样例 #3

输入 #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$。

由 ChatGPT 4.1 翻译