You are the mayor of a very old city. The city has n major tourist attractions. You are given the locations (x, y, z) for each of these tourist attractions.
To boost the tourism in your city, you plan to create new roads that connect the tourist attractions.
To create a bidirectional road between tourist attraction A (located at (x1, y1, z1)) and B (located at (x2, y2, z2)), you need to spend min( |x1 - x2| , |y1 - y2| , |z1 - z2| ) dollars. Here |x1 - x2| refers to the absolute value of x1 - x2, and min(x, y, z) refers to the minimum value out of x, y and z.
You need to create a network of roads such that it is possible to travel between any pair of tourist attractions using some sequence of roads. What is the minimum amount of dollars you need to spend in order to accomplish this task?
Sample Input
n = 3
locations =
[[1,5,7],
[2,9,4],
[1,3,9]]
Expected Output
1
Explanation
We can create 2 roads -
Road connecting attraction 1 (at (1, 5, 7)) and attraction 3 (at (1, 3, 9)). The cost of creating this road is min ( | 1 - 1 | , | 5 - 3 | , | 7 - 9 | ) = min ( 0 , 2 , 2 ) = 0.
Road connecting attraction 1 (at (1, 5, 7)) and attraction 2 (at (2, 9, 4)). The cost of creating this road is min ( | 1 - 2 | , | 5 - 9 | , | 7 - 4 | ) = min ( 1 , 4 , 3 ) = 1.
Creating these two roads enables us to travel between any pair of tourist attractions.
The total cost of creating these roads is 1 dollar.
[execution time limit] 1 seconds (cpp)
[input] integer n
The number of major tourist attractions in the city
2 <= n <= 100000
[input] array.array.integer locations
A matrix consisting of n rows. Each row has 3 integers - Xi, Yi, Zi - which describe the location of the ith attraction.
All coordinates are integers, and
-100000 <= Xi, Yi, Zi <= 100000 for all i.
[output] integer64
The minimum amount in dollars that you need to spend in order to build the road network.