VNEMPIRE - Đế chế
Giới hạn- Thời gian: 0.4s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
- Người up: tranhaidangfpt
- Nguồn bài: COCI 2010 contest 7