Uber 28 Q1 :
Difficulty Level : Hard
Submissions : 199
Asked In :
Marks :10
: 2 | : 0
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 tourist attraction.
To boost tourism in your city, you can plan to create new roads that connect tourist attractions.
To create a bidirectional road between tourist attraction A (located at $$$(x_1, y_1, z_1)$$$) and B (located at $$$(x_2, y_2, z_2)$$$), you need to spend $$$min(|x_1 - x_2|, |y_1 - y_2|, |z_1 - z_2|)$$$ dollars. Here $$$|x_1 - x_2|$$$ refers to the absolute value of $$$x_1 - x_2$$$, 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 to accomplish this task?
The first line contains an integer $$$n$$$ $$$(2 \le n \le 10^5)$$$, denoting the number of major tourist attractions. The following $$$n$$$ lines contain three space-separated integers $$$x_i, y_i \& z_i$$$ $$$(-10^5 \le x_i, y_i, z_i \le 10^5)$$$, the locations of these tourist attractions.
The minimum number of dollars that you need to spend.
3 1 5 7 2 9 4 1 3 9
1
