斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。-------- 百度百科
在图论里，一般用于解决形如：
给定一个连通图 \(G\)，给定 \(k\) 个关键点，选取一些边使得 \(k\) 个关键点连通，要求权值和最小。
最小生成树可以看作是一种特殊的斯坦纳树。
我们不难想到，给出的 \(k\) 个点可能并不能只用连接这 \(k\) 个点的边达到连通，有可能需要另外 \(n-k\) 个点的中转；其次，可能经过外面 \(n-k\) 个点中的点的中转，可以让边权和更小。
我们发现 \(k\) 很小，所以可以使用状压来试试。
我们用 \(f[i][S]\) 表示以 \(i\) 为根的树，包含 \(S\) 内所有点的最小边权值和。
首先我们知道最后形成的是一棵树，不难想到最后有个环的话去掉最大的那条边也可以。
我们考虑如何转移状态：
其中 \(subs\) 是 \(s\) 状态的一个子集，这个是保证一开始 \(f[i][s]\) 尽量小。
/*
* @Author: Aisaka_Taiga
* @Date: 2023-10-02 17:28:45
* @LastEditTime: 2023-10-02 19:27:11
* @LastEditors: Aisaka_Taiga
* @FilePath: \Desktop\P6192.cpp
* The heart is higher than the sky, and life is thinner than paper.
*/
#include <bits/stdc++.h>
#define pii pair<int, int>
#define INF 0x3f3f3f3f
#define int long long
#define M 5010
#define N 510
using namespace std;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
while(c <= '9' && c >= '0') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return x * f;
}
int n, m, k, cnt, head[M], f[N][M], vis[N], key[N];
struct node{int u, v, w, next;}e[N << 1];
priority_queue<pii, vector<pii>, greater<pii> > q;
inline void add(int u, int v, int w){e[++ cnt] = (node){u, v, w, head[u]}; head[u] = cnt;}
inline void Dij(int s)
{
memset(vis, 0, sizeof vis);//清空vis
while(!q.empty())
{
int u = q.top().second;//取出当前点
q.pop();
if(vis[u]) continue;//如果之前找过了就不用遍历了
vis[u] = 1;//打标记
for(int i = head[u]; i; i = e[i].next)
{
int v = e[i].v;//终点
if(f[v][s] <= f[u][s] + e[i].w) continue;//如果加入了这条边边权和更大了就不加
f[v][s] = f[u][s] + e[i].w;//松弛
q.push({f[v][s], v});//入堆
}
}
return ;
}
signed main()
{
memset(f, INF, sizeof f);
n = read(), m = read(), k = read();
for(int i = 1; i <= m; i ++)
{
int u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, w);
}
for(int i = 1; i <= k; i ++)
{
key[i] = read();
f[key[i]][1 << (i - 1)] = 0;//以关建点为根，只包含当前点的代价是0
}
for(int s = 1; s <= (1 << k); s ++)//枚举k个点的所有状态
{
for(int i = 1; i <= n; i ++)//枚举每一个点
{
for(int subs = s & (s - 1); subs; subs = s & (subs - 1))//枚举每一个子集
f[i][s] = min(f[i][s], f[i][subs] + f[i][s ^ subs]);//DP取最小值
if(f[i][s] != INF) q.push({f[i][s], i});//只要不是全是INF就可以试试
}
Dij(s);//跑DIJ
}
cout << f[key[1]][(1 << k) - 1] << endl;//输出以1为根的子树所有关键点都在里面最小的边权和
return 0;
}