Đế chế

View as PDF

Submit solution


Points: 0.29 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
COCI 2010 contest 7
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một đế chế đang xây dựng mạng lưới cho các hành tinh trong nó. Đế chế gồm có ~N~ hành tinh được biểu diễn như các điểm trong không gian ~3~ chiều. Chi phí phải chi cho việc nối giữa hành tinh ~A~ và hành tinh ~B~ là ~min{(|x_A - x_B|, |y_A - y_B|, |z_A - z_B|)}~ với ~(x_A, y_A, z_A), (x_B, y_B, z_B)~ là tọa độ của hành tinh ~A~, ~B~ trong không gian ~3~ chiều. Đế chế dự tính sẽ xây dựng ~N-1~ cầu nối như vậy để các hành tinh liên thông với nhau và chi phí để trả sao cho phải nhỏ nhất có thể.

Input

  • Dòng đầu là số hành tinh ~N~ (~N < 100001~).
  • ~N~ dòng sau mỗi dòng là tọa độ của một hành tinh.

Output

Ghi trên một dòng duy nhất chi phí nhỏ nhất có thể.

Sample Input

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

Sample Output

4

Comments

Please read the guidelines before commenting.


There are no comments at the moment.