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$ 的最小总花费。

### 限制条件 - $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 翻译