a307. TOI 2023/05 潛力組：糧食便道

題目描述

N 個城鎮原本的道路都無法通行，其中 K 個城鎮可以生產糧食。你可以從 M 條候選的無向便道中選擇一些興建，每條便道都有指定成本。

請讓每個城鎮都能經由建好的便道，到達至少一個生產糧食的城鎮，並使總建造成本最小。生產糧食的城鎮本身已符合條件，不需要彼此連通。

輸入格式

第一行為 N、M、K。第二行為 K 個由小到大排列且互不相同的糧食生產城鎮編號。接著 M 行各有 A、B、C，表示在 A 與 B 之間建便道的成本是 C。

• 2 ≤ N ≤ 200000
• 1 ≤ M ≤ min(N(N−1)/2,1000000)
• 1 ≤ K ≤ N
• 城鎮編號為 1 到 N，1 ≤ A < B ≤ N
• 1 ≤ C ≤ 10000；同一對城鎮最多一條候選便道。
• 保證存在可行方案。

輸出格式

輸出最低總建造成本。

來源

TOI 2023 年 5 月底潛力組〈糧食便道〉。以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202305/Supply.pdf 題意核對鏡像：https://zerojudge.tw/ShowProblem?problemid=k715