Svemir
플래티넘 V의견: 0
Fourth Great and Bountiful Human Empire is developing a transconduit tunnel network connecting all its planets. The Empire consists of \(N\) planets, represented as points in 3D space. The cost of forming a transconduit tunnel between planets \(A\) and \(B\) is:
$$ \mathrm{TunnelCost}[A, B] = \min\{\, |x_A - x_B|,\ |y_A - y_B|,\ |z_A - z_B| \,\} $$
where \((x_A, y_A, z_A)\) are the 3D coordinates of planet \(A\), and \((x_B, y_B, z_B)\) are the 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 a chain of links.
You need to come up with the lowest possible cost of successfully completing this project.
The first line of input contains one integer \(N\) (\(1 \le N \le 100\,000\)), the number of planets.
The 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.
The first and only line of output should contain the minimal cost of forming
the network of tunnels.
SAMPLE TEST CASES
Input:
2
Input:
3
-\(1 -1 -1\)
Input:
5
\(11 -15 -15\)
1 5 10
7 8 2
5 5 5
10 10 10
\(14 -5 -15\)
-\(1 -1 -5\)
\(10 -4 -1\)
\(19 -4\ 19\)
Output:
3
Output:
11
Output:
4
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Test 1 | 10점 | None |
Test 2 | 10점 | None |
Test 3 | 10점 | None |
Test 4 | 10점 | None |
Test 5 | 10점 | None |
Test 6 | 10점 | None |
Test 7 | 10점 | None |
Test 8 | 10점 | None |
Test 9 | 10점 | None |
Test 10 | 10점 | None |
2
11 -15 -15
14 -5 -1533
-1 -1 -1
1 5 10
-1 -1 -5115
7 8 2
5 5 5
10 10 10
10 -4 -1
19 -4 194평가 및 의견
Svemir
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Svemir