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$ $\vdots$ $X_N$ $Y_N$ $Z_N$

输出格式

输出从城市 $1$ 出发，至少访问每个其他城市一次，并返回城市 $1$ 的最小总代价。

2
0 0 0
1 2 3

9

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

10

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

6519344

提示

$2 \leq N \leq 17$ $-10^6 \leq X_i,Y_i,Z_i \leq 10^6$ 没有两个城市位于相同的点。 输入中的所有数值均为整数。从城市 $1$ 到城市 $2$ 的代价是 $|1-0|+|2-0|+\max(0,3-0)=6$。 从城市 $2$ 到城市 $1$ 的代价是 $|0-1|+|0-2|+\max(0,0-3)=3$。 因此，总代价为 $9$。
例如，我们可以按顺序 $1$、$2$、$1$、$3$、$1$ 访问城市，使总代价为 $10$。注意我们可以在途中回到城市 $1$。

标签: AtCoder|abc180E

来源

AtCoder|abc180E