TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

14.3% (3/21)

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

2
3 3
0 6 1
0 0 1
8 0 1
3 0
0 6 0
0 0 0
8 0 0

Sample Output

3
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 12000 65536 262144 1
1 12000 65536 262144 2
2 12000 65536 262144 3
3 12000 65536 262144 4
4 12000 65536 262144 5
5 12000 65536 262144 6
6 12000 65536 262144 7
7 12000 65536 262144 8
8 12000 65536 262144 9
9 12000 65536 262144 10