有一個國家，他裡面有 $N$ 個城市 (城市以 $1$ 到 $N$ 進行編號)，以及有 $M$ 條管線。
第 $i$ 條管線連接編號為 $a_i$ 及編號 $b_i$ 的國家，並且如果要建造這條管線需要花 $c_i$ 的錢。
管線可能連接相同的城市 ($a_i = b_i$)。
除此之外，每個城市都有條件可以建水庫 (蓄水池)，只是貴和便宜而已，他們可以花 $w_i$ 塊錢的成本去建造水庫。
現在，你打算讓每一個城市都有水可以用。城市可以由以下兩種方式來取得自來水：
1. 開採石油井
2. 透過道路，連接一個已經有水庫的城市 (不用管道路多遠，有連到就可以)
請你透過程式來告訴政府最少需要花多少錢才能讓每個城市都有自來水可用？
第一行有兩個正整數 $N$、$M$，代表城市的個數及管線的數量
接下來的一行包含 $N$ 個正整數 $w_1,\ w_2,\ \dots\ ,\ w_N$，$w_i$ 代表第 $i$ 個城市建造水庫的費用。
接下來的 $M$ 行每一行包含三個正整數 $a_i$、$b_i$、$c_i$，代表第 $i$ 條管線連接 $a_i$、$b_i$ 兩座城市，且建造的成本是 $c_i$
輸出一個正整數，代表最低的成本
9 10 3 1 4 1 5 9 2 6 5 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7
30
前 $20\%$ 測資：$1 \leq N \leq 200,\ 0 \leq M \leq 200$
前 $40\%$ 測資：$1\leq N \leq 10000,\ 0 \leq M \leq 10000$
對於所有測資：$1\leq N \leq 2 \times 10^5,\ 0 \leq M \leq 10^6,\ 1 \leq a_i,b_i \leq N,\ 1 \leq c_i,w_i\ \leq 10^9$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||