內容
颱風過後OI國所有城鎮之間的聯絡道路交通中斷，讓糧食供應產生問題。
國王想要搭建一些無向便道，使得每個城鎮至少和一個有生產糧食的城鎮連通，並且將搭建便道的總成本最小化。
以下圖為例，假設有N = 8個城鎮，編號1至 8。城鎮3以及城鎮8有生產糧食。
圖中圓圈代表城鎮，裡面的數字代表城鎮的編號，旁邊有星形符號表示該城鎮有生產糧食；連接兩相異城鎮的線段代表可能在此二城鎮間搭建糧食便道，線段旁的數字代表搭建成本。
此例中的最佳解如圖二所示，總成本為10。
輸入說明
第一列有三個正整數N、M和K ( 2≤ N ≤ 2×105, M ≤ min( N×(N-1)/2, 106), K ≤ N )，表示有N個城鎮（編號1, ..., N）、M筆候選便道的資訊以及有K個城鎮有生產糧食。
第二列有K個正整數X1, …, XK (X1 < …< XK)，相鄰的兩數皆以一個空白隔開，表示生產糧食的城鎮編號。
接下來M列，第 i+2列有三個正整數Ai, Bi, Ci (1≤ Ai < Bi ≤ N, 1 ≤ Ci ≤ 104)，相鄰的兩數皆以一個空白隔開，表示在城鎮Ai和Bi間搭建一條無向便道的成本為Ci。兩個城鎮之間最多只會有一條無向便道。
輸出說明
請輸出一非負整數，表示能使得每個城鎮至少和一個有生產糧食的城鎮連通的最低搭建成本。
範例輸入
#1
8 13 2 3 8 1 2 2 1 3 3 1 4 7 2 3 2 2 4 3 2 5 4 3 6 4 3 7 3 4 5 1 6 5 1 6 8 2 5 8 4 7 8 2
範例輸出
#1
10
範例輸入
#2
7 10 1 2 1 3 2 1 4 4 2 3 3 2 5 1 2 6 3 2 7 3 3 4 4 3 6 4 4 6 5 5 7 2
範例輸出
#2
15
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (16%): 1.0s , <1K
公開 測資點#1 (16%): 1.0s , <1K
公開 測資點#2 (17%): 1.0s , <1K
公開 測資點#3 (17%): 1.0s , <1K
公開 測資點#4 (17%): 1.0s , <1K
公開 測資點#5 (17%): 1.0s , <1K
公開 測資點#0 (16%): 1.0s , <1K
公開 測資點#1 (16%): 1.0s , <1K
公開 測資點#2 (17%): 1.0s , <1K
公開 測資點#3 (17%): 1.0s , <1K
公開 測資點#4 (17%): 1.0s , <1K
公開 測資點#5 (17%): 1.0s , <1K
提示 ：
標籤:
出處:
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||