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 


Được gửi lên bởi:Trần Hải Đăng
Ngày:2010-05-03
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:COCI 2010 contest 7

hide comments
2017-04-02 17:29:49
test yếu :v
2017-03-08 15:10:00
one hit and 100 dòng :)
2016-10-07 14:31:25
sao lại ra 4 được phải là 7 chứ
2016-08-01 07:14:55
Nộ long cước....
2016-05-27 16:02:12
cái máy thần thánh 0 khai báo hàm hay thủ tục mà nó vẫn dịch và chạy đúng, hại nộp lên đây bị lỗi mấy lần @@@
2016-05-21 14:24:15
4 lần sort chỉ cần viết 2 thủ tục thôi :)))))))
2015-10-13 12:45:36 Tuấn IGaMing
Krk + sort 3 lần
2015-09-12 14:29:01
mình gà mía nên mình quicksort 4 lần há :)))
2015-07-29 09:55:33 N�ng D�n John
Vãi bài, 4 quicksort :)
2015-01-04 17:36:55 Sơn Tùng M-TP


Last edit: 2016-12-15 16:20:23
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.