1727 . Spore
TopCoder
Tags
Description
Spore是一個Maxis開發的由多種遊戲類型整合的電腦遊戲。
遊戲讓玩家控制一個物種，使之從單細胞開始進化到智慧生命，進而進行空間探索。
你好不容易進入了文明階段，開發出了海底電纜和衛星網路。
現在你有N個城市，為了加強聯繫，你打算建立起一個通訊網路，使任兩個城市都能直接或間接的通訊。
要使用衛星網路需要有衛星收發器，現在有K台衛星收發器，任意兩個擁有衛星收發器的城市可以互相通訊。
其他的城市可以則可以透過架設海底電纜通訊。
海底電纜的價格是長度的平方。
然後把各台衛星發射器運送到目標城市，需要一些空運費用。
那麼給你N個城市的座標，以及你手上有K台衛星收發器。
要怎麼分配這K台衛星收發器才能使鋪設整個通訊網路的花費最小。
Input Format
輸入的第一行會有一個整數T，表示有T筆測試資料。(T <= 5)
每筆測試資料的第一行會有兩個整數N, K，表示城市數量和衛星設備數量。
接下來會有N行，每行有三個整數X_i, Y_i, C_i，表示第i個城市的座標，以及把一台衛星收發器空運到i城市需要花C_i元。
(1 <= N <= 2000, 0 <= K < 231, 0 <= X_i, Y_i <= 10000, 0 <= C_i <= 10000)
你可以假設任兩個城市不會在同個座標。
Output Format
輸出會有T行，對於每筆測試資料輸出一個整數表示最小花費。
Sample Input 1
2
3 3
0 6 1
0 0 1
8 0 1
3 0
0 6 0
0 0 0
8 0 0
3 3
0 6 1
0 0 1
8 0 1
3 0
0 6 0
0 0 0
8 0 0
Sample Output 1
3
100
100
Hints
第2筆測試資料，
將1 2的城市架設海底電纜，2 3的城市架設海底電纜，長度分別為6和8。
總價為 36 + 64 = 100。
Problem Source
原TIOJ1727 / Problem Setter : yuscvscv
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |