← 返回题目列表

AtCoder · abc180_e

E. 空中城市间的旅行推销员

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

在三维空间中,有 N 城市: 城市 1 穿越城市 N。城市 i 位于该点 (X_i,Y_i,Z_i).

从某个城市前往某个点所需的费用 (a,b,c) 前往某个城市 (p,q,r) is |p-a|+|q-b|+\max(0,r-c).

求从城市开始所需的最低总成本 1,访问所有其他城市至少一次,然后返回城市 1.

约束

  • 2 \leq N \leq 17
  • -10^6 \leq X_i,Y_i,Z_i \leq 10^6
  • 没有两个城市处于同一点。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
X_1 Y_1 Z_1
\vdots
X_N Y_N Z_N

输出

打印从城市开始所需的最低总成本 1,访问所有其他城市至少一次,然后返回城市 1.


示例输入 1

2
0 0 0
1 2 3

示例输出 1

9

从城市出发的交通费用 1 前往城市 2 is |1-0|+|2-0|+\max(0,3-0)=6.

从城市出发的交通费用 2 前往城市 1 is |0-1|+|0-2|+\max(0,0-3)=3.

因此,总成本将为 9.


示例输入 2

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

示例输出 2

10

例如,我们可以按顺序访问城市 1, 2, 1, 3, 1 使总成本 10。请注意,我们可以回到城市 1 正在路上。


示例输入 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