ĐẾ CHẾ

Nguồn: http://vn.spoj.com/problems/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 vào: Từ tệp văn bản DECHE.INP

+ 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.

Dữ liệu ra: Ghi vào tệp DECHE.OUT

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

Ví dụ:

DECHE.INP	DECHE.OUT
5 11 -15 -15 14 -5 -15 -1 -1 -5 10 -4 -1 19 -4 19	4

 SOLUTION - CODE - TEST