| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P135SUMJ - SUM5 J - Mạng lưới giao thông trong thiên hà |
Trong giấc mơ, Tèo thấy mình trở thành một ông vua vĩ đại của cả một thiên hà. Đang trong giai đoạn phát triển, Tèo muốn xây dựng hệ thống đường hầm không gian để di chuyển giữa các hành tinh trong thiên hà. Chi phí đường hầm giữa 2 hành tinh A và B bằng:
Chi phí đường hầm giữa [A,B] = min{ |xA-xB|, |yA-yB|, |zA-zB| }
(xA, yA, zA) và (xB, yB, zB) lần lượt là tọa độ của 2 hành tinh A và B. Thiên hà của Tèo có tất cả N hành tinh, và cần xây dựng tất cả N-1 đường hầm để có thể kết nối tất cả các hành tinh.
Các bạn hãy giúp Tèo tính toán chi phí nhỏ nhất để có thể hoàn thành nhiệm vụ này.
Input
Dòng đầu tiên là số lượng hành tinh N (1 ≤ N ≤ 100 000).
N dòng tiếp theo, mỗi dòng gồm 3 số nguyên có giá trị nằm trong khoảng -10^9 tới 10^9.
Không có hai hành tinh tinh nào có cùng tọa độ.
Output
In ra một dòng duy nhất là chi phí nhỏ nhất để xây dựng được hệ thống đường hầm trong thiên hà.
Example
Test 1:
Input:
2
1 5 10
7 8 2
Output:
3
Test 2:
Input:
3
-1 -1 -1
5 5 5
10 10 10
Output:
11
Test 3:
Input:
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
Output:
4
| Được gửi lên bởi: | adm |
| Ngày: | 2013-08-09 |
| Thời gian chạy: | 2s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
