分数: 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