#P5180. [Baltic2016]Cities
[Baltic2016]Cities
Description
给定n个点,m条双向边的图。其中有k个点是重要的。每条边都有一定的长度。
现在要你选定一些边来构成一个图,要使得k个重要的点相互连通,求边的长度和的最小值。
Format
Input
共m+2行
第1行:n,k,m,n个点,k个重要的点,m条边;
第 2 行给出 个重要点的编号。
第3至第m+2行,每行包括3个数字,a,b,c,表示有一条从a到b长度为c的双向路径
,,,,。原图任意两座城市之间均可经道路到达,因此总有可行方案。
Output
共1行,即最小长度和
Samples
4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8
11