VNEMPIRE - Đế chế

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 


Added by:Trần Hải Đăng
Date:2010-05-03
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:COCI 2010 contest 7

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.