A6203. 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$ 的最小总花费。
从坐标为 $(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$
> $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$。
- $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$。