q672.
pD. 帕拉迪島攻防戰
內容
在帕拉迪島上住著各種巨人，
除了進擊巨人、鎧甲巨人之外，還有矮之巨人、談之巨人、槍之巨人等等。
已知島上有多個城鎮，部分城鎮中住著巨人，
為了讓巨人能守護所有城鎮，你希望在城鎮與城鎮間建立雙向道路，每個道路皆有需付出的成本。
在確保每個城鎮都可透過直接或間接的道路與至少一個居住著巨人的城鎮相連的情況下，建立道路的總成本最小可為多少？
以下圖為例，總共有 6 個城鎮(編號 1 ~ 6)，
圓圈內的數字代表城鎮編號，線段旁的數字則代表建立該道路所需成本，其中編號2、4的城鎮住著巨人。
最佳解如右圖所示，總成本為 140 元。
輸入說明
第一行有三個正整數 N, M, K，代表總共有 N 個城鎮(編號 1 ~ N)、M 條可建立的雙向道路、其中 K 個城鎮住有巨人
2 ≤ N ≤ 200000
1 ≤ M ≤ min(N*(N-1)/2, 1000000)
1 ≤ K ≤ N
第二行有 K 個正整數 ai，代表編號 ai 的城鎮住有巨人
1 ≤ ai ≤ N
最後有 M 行，每行有三個正整數 u, v, c
代表城鎮 u 和 v 之間可以建立一條成本為 c 的雙向道路，並且不會有重邊發生
1 ≤ u, v ≤ N
1 ≤ c ≤ 10000
輸出說明
每個城鎮都與至少一個居住巨人的城鎮連通的情況下，
最小建立道路總成本，其中每筆測試資料保證有解
範例輸入
#1
6 10 2 2 4 1 2 40 1 3 50 1 4 30 2 3 10 2 5 40 3 4 20 3 5 50 3 6 70 4 6 60 5 6 60
範例輸出
#1
140
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (5%): 2.0s , <10M
公開 測資點#1 (5%): 2.0s , <10M
公開 測資點#2 (5%): 2.0s , <10M
公開 測資點#3 (5%): 2.0s , <1M
公開 測資點#4 (5%): 2.0s , <10M
公開 測資點#5 (5%): 2.0s , <10M
公開 測資點#6 (5%): 2.0s , <1K
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1K
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1K
公開 測資點#12 (5%): 2.0s , <10M
公開 測資點#13 (5%): 2.0s , <50M
公開 測資點#14 (5%): 2.0s , <10M
公開 測資點#15 (5%): 2.0s , <10M
公開 測資點#16 (5%): 2.0s , <10M
公開 測資點#17 (5%): 2.0s , <50M
公開 測資點#18 (5%): 2.0s , <50M
公開 測資點#19 (5%): 2.0s , <50M
公開 測資點#0 (5%): 2.0s , <10M
公開 測資點#1 (5%): 2.0s , <10M
公開 測資點#2 (5%): 2.0s , <10M
公開 測資點#3 (5%): 2.0s , <1M
公開 測資點#4 (5%): 2.0s , <10M
公開 測資點#5 (5%): 2.0s , <10M
公開 測資點#6 (5%): 2.0s , <1K
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1K
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1K
公開 測資點#12 (5%): 2.0s , <10M
公開 測資點#13 (5%): 2.0s , <50M
公開 測資點#14 (5%): 2.0s , <10M
公開 測資點#15 (5%): 2.0s , <10M
公開 測資點#16 (5%): 2.0s , <10M
公開 測資點#17 (5%): 2.0s , <50M
公開 測資點#18 (5%): 2.0s , <50M
公開 測資點#19 (5%): 2.0s , <50M
提示 ：
30% 只有 1 個城鎮住著巨人
30% 最多 100 個城鎮
40% 無限制
出處:
114學年度
hgsh
校內賽
[管理者：
mushroom.cs9
...
(mushroom)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 46168 |
|
q672 | 121 | 2025-06-03 01:00 |