#P5180. [Baltic2016]Cities

    ID: 4249 传统题 1000ms 256MiB 尝试: 362 已通过: 75 难度: 7 上传者: 标签>CF2300提高+/省选-子集 DPDijkstra子掩码递推 (s-1)&mask二叉堆对称性去重

[Baltic2016]Cities

Description

给定n个点,m条双向边的图。其中有k个点是重要的。每条边都有一定的长度。

现在要你选定一些边来构成一个图,要使得k个重要的点相互连通,求边的长度和的最小值。

Format

Input

共m+2行

第1行:n,k,m,n个点,k个重要的点,m条边;

第 2 行给出 kk 个重要点的编号。

第3至第m+2行,每行包括3个数字,a,b,c,表示有一条从a到b长度为c的双向路径

2≤k≤52\le k\le5,k≤n≤105k\le n\le10^5,1≤m≤2×1051\le m\le2\times10^5,1≤a,b≤n1\le a,b\le n,1≤c≤1091\le c\le10^9。原图任意两座城市之间均可经道路到达,因此总有可行方案。

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

题目来源