2164 . 運送蛋餅

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

80.6% (112/139)

Submission's AC Ratio

22.5% (174/775)

Tags

CKcon 2020-CKcon

Description

在我們生存的宇宙以外，有另一個宇宙被稱為蛋餅宇宙。在蛋餅宇宙中有 n 間早餐店，其中第 i 間早餐店的座標位置為 (xi,yi,zi)。
蛋餅宇宙的居民都很喜歡吃蛋餅，為了舉辦蛋餅交流大會，他們決定在早餐店之間設置蛋餅傳送門。其中，在第 i 和第 j 間早餐店之間設置傳送門需要花費 (xi−xj)2+(yi−yj)2+(zi−zj)2 的成本，設置完成後第 i 間早餐店便可以運送蛋餅到第 j 間；第 j 間早餐店也可以運送蛋餅到第 i 間。
因為蛋餅宇宙的居民不是很有錢，請幫他們計算如果想讓每一間早餐店都可以透過一些傳送門運送蛋餅到任意一間早餐店至少需要花費多少成本。

保證任何兩間早餐店的座標都不相同

Input Format

第一行有一個正整數 n
接下來 n 行有三個整數 xi,yi,zi

n≤5000
|xi|,|yi|,|zi|≤105

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

Sample Output 1

369

Sample Input 2

2
-1 -8 10
-6 8 -7

Sample Output 2

570

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~4 n≤3;|xi|,|yi|≤10 9
2 0~9 n≤100 30
3 10~14 ∀1≤i≤n,yi=zi=0 11
4 0~49 No additional constraints. 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 4
1 1000 524288 65536 1 2 4
2 1000 524288 65536 1 2 4
3 1000 524288 65536 1 2 4
4 1000 524288 65536 1 2 4
5 1000 524288 65536 2 4
6 1000 524288 65536 2 4
7 1000 524288 65536 2 4
8 1000 524288 65536 2 4
9 1000 524288 65536 2 4
10 1000 524288 65536 3 4
11 1000 524288 65536 3 4
12 1000 524288 65536 3 4
13 1000 524288 65536 3 4
14 1000 524288 65536 3 4
15 1000 524288 65536 4
16 1000 524288 65536 4
17 1000 524288 65536 4
18 1000 524288 65536 4
19 1000 524288 65536 4
20 1000 524288 65536 4
21 1000 524288 65536 4
22 1000 524288 65536 4
23 1000 524288 65536 4
24 1000 524288 65536 4
25 1000 524288 65536 4
26 1000 524288 65536 4
27 1000 524288 65536 4
28 1000 524288 65536 4
29 1000 524288 65536 4
30 1000 524288 65536 4
31 1000 524288 65536 4
32 1000 524288 65536 4
33 1000 524288 65536 4
34 1000 524288 65536 4
35 1000 524288 65536 4
36 1000 524288 65536 4
37 1000 524288 65536 4
38 1000 524288 65536 4
39 1000 524288 65536 4
40 1000 524288 65536 4
41 1000 524288 65536 4
42 1000 524288 65536 4
43 1000 524288 65536 4
44 1000 524288 65536 4
45 1000 524288 65536 4
46 1000 524288 65536 4
47 1000 524288 65536 4
48 1000 524288 65536 4
49 1000 524288 65536 4
Submit
Back to Top