2164 . 運送蛋餅
TopCoder
Tags
Description
在我們生存的宇宙以外，有另一個宇宙被稱為蛋餅宇宙。在蛋餅宇宙中有 $n$ 間早餐店，其中第 $i$ 間早餐店的座標位置為 $(x_i, y_i, z_i)$。
蛋餅宇宙的居民都很喜歡吃蛋餅，為了舉辦蛋餅交流大會，他們決定在早餐店之間設置蛋餅傳送門。其中，在第 $i$ 和第 $j$ 間早餐店之間設置傳送門需要花費 $(x_i-x_j)^ 2 + (y_i-y_j)^ 2 + (z_i-z_j)^ 2$ 的成本，設置完成後第 $i$ 間早餐店便可以運送蛋餅到第 $j$ 間；第 $j$ 間早餐店也可以運送蛋餅到第 $i$ 間。
因為蛋餅宇宙的居民不是很有錢，請幫他們計算如果想讓每一間早餐店都可以透過一些傳送門運送蛋餅到任意一間早餐店至少需要花費多少成本。
保證任何兩間早餐店的座標都不相同
Input Format
第一行有一個正整數 $n$
接下來 $n$ 行有三個整數 $x_i, y_i, z_i$
$n \leq 5000$
$|x_i|, |y_i|, |z_i| \leq 10^ 5$
Output Format
輸出一個非負整數代表答案
Sample Input 1
7
-2 7 -3
-4 -1 -7
-1 -6 -1
-3 1 -1
-5 -3 -10
7 3 -10
1 4 6
-2 7 -3
-4 -1 -7
-1 -6 -1
-3 1 -1
-5 -3 -10
7 3 -10
1 4 6
Sample Output 1
369
Sample Input 2
2
-1 -8 10
-6 8 -7
-1 -8 10
-6 8 -7
Sample Output 2
570
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | $ n \leq 3; |x_i|,|y_i| \leq 10$ | 9 |
| 2 | 0~9 | $ n \leq 100 $ | 30 |
| 3 | 10~14 | $\forall 1 \leq i \leq n, y_i=z_i=0$ | 11 |
| 4 | 0~49 | No additional constraints. | 50 |