Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vnempire

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