====================================
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{ |xA - xB|, |yA - yB|, |zA -
zB| } với (xA, yA, zA), (xB, yB, zB) 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ể.
Dữ liệu
- 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.
Kết qủa
Ghi
trên một dòng duy nhất chi phí nhỏ nhất có thể.
Ví dụ
Dữ liệu
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
Kết qủa
4
Solution: VNEMPIRE
Code: VNEMPIRE.PAS