Svemir
Fourth Great and Bountiful Human Empire is developing a transconduit tunnel network connecting all it's planets. The Empire consists of N planets, represented as points in the 3D space. The cost of forming a transconduit tunnel between planets A and B is:
TunnelCost[A,B] = min{ |xA-xB|, |yA-yB|, |zA-zB| }
where (xA, yA, zA) are 3D coordinates of planet A, and (xB, yB, zB) are coordinates of planet B. The Empire needs to build exactly N - 1 tunnels in order to fully connect all planets, either by direct links or by chain of links. You need to come up with the lowest possible cost of successfully completing this project.
Input:
Output:
Input:
Output:
Input:
Output:
TunnelCost[A,B] = min{ |xA-xB|, |yA-yB|, |zA-zB| }
where (xA, yA, zA) are 3D coordinates of planet A, and (xB, yB, zB) are coordinates of planet B. The Empire needs to build exactly N - 1 tunnels in order to fully connect all planets, either by direct links or by chain of links. You need to come up with the lowest possible cost of successfully completing this project.
InputThe first line of input contains one integer N (1 ≤ N ≤ 100 000), number of planets. Next N lines contain exactly 3 integers each. All integers are between -10^9 and 10^9 inclusive. Each line contains the x, y, and z coordinate of one planet (in order).
No two planets will occupy the exact same point in space.
No two planets will occupy the exact same point in space.
OutputThe first and only line of output should contain the minimal cost of forming the network of tunnels.
Input:
2
1 5 10
7 8 2Output:
3 Input:
3
-1 -1 -1
5 5 5
10 10 10Output:
11 Input:
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19Output:
4 Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.