P12220 [蓝桥杯 2023 国 Java B] 星球

小明驾驶飞船对某星系发起攻击。星系中有 $n$ 颗星球，编号依次是 $1, 2, \ldots, n$。第 $i$ 颗星球的坐标为 $(x_i, y_i, z_i)$，且其防御强度为 $w_i$。 小明需要规划出进攻这 $n$ 颗星球的顺序使得其进攻所需能量最少。 对于一个遍历顺序 $p_1, p_2, \ldots, p_n$ 来说，小明进攻需要的能量为 $E = \displaystyle \sum_{i=2}^{n} d(p_{i-1}, p_i) \times w_{p_i}$，其中 $d(p_{i-1}, p_i)$ 表示 $p_{i-1}, p_i$ 两颗星球之间的直线距离。小明想知道进攻所需最少能量是多少。

输入共 $n + 1$ 行。 第一行为一个正整数 $n$。 后面 $n$ 行，每行四个整数 $x_i, y_i, z_i, w_i$。

输出共 $1$ 行，一个浮点数（保留两位小数）。

### 样例说明 当进攻顺序为 $\{1, 2, 3\}$ 时，所需能量最小，为 $5\sqrt{5} + 3\sqrt{6}$。 ### 评测用例规模与约定 - 对于 $20\%$ 的数据，保证 $n \leq 8$。 - 对于 $100\%$ 的数据，保证 $n \leq 18$，$0 \leq x_i, y_i, z_i, w_i \leq 100$。