[AdditionalFile187.zip](file://AdditionalFile187.zip?type=additional_file)

Description

【题意】
给定一个包含 $n$ 个结点和 $m$ 条带权边的无向连通图 $G=(V,E)$。
再给定包含 $k$ 个结点的点集 $S$，选出 $G$ 的子图 $G'=(V',E')$，使得：
1. $S\subseteq V'$；
2. $G'$ 为连通图；
3. $E'$ 中所有边的权值和最小。
你只需要求出 $E'$ 中所有边的权值和。

【输入格式】
第一行：三个整数 $n,m,k$，表示 $G$ 的结点数、边数和 $S$ 的大小。
接下来 $m$ 行：每行三个整数 $u,v,w$，表示编号为 $u,v$ 的点之间有一条权值为 $w$ 的无向边。
接下来一行：$k$ 个互不相同的正整数，表示 $S$ 的元素。

【输出格式】
第一行：一个整数，表示 $E'$ 中边权和的最小值。

【样例输入】
7 7 4
1 2 3
2 3 2
4 3 9
2 6 2
4 5 3
6 5 2
7 6 4
2 4 7 5

【样例输出】
11

【样例解释】
样例中给出的图如下图所示，红色点为 $S$ 中的元素，红色边为 $E'$ 的元素，此时 $E'$ 中所有边的权值和为 $2+2+3+4=11$，达到最小值。


【数据范围】
对于 $100\%$ 的数据，$1\leq n\leq 100,\ \ 1\leq m\leq 500,\ \ 1\leq k\leq 10,\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^6$。
保证给出的无向图连通，但 **可能** 存在重边和自环。

Hint

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=110, INF=0x3f3f3f3f;
vector<PII>G[N];
int n,dp[N][1<<10],vis[N],a[N];
void dijkstra(int s)
{
	memset(vis, 0, sizeof(vis));
    priority_queue<PII,vector<PII>,greater<PII>> q;
	for(int i=1;i<=n;i++)if(dp[i][ s ]!=INF)q.push({dp[i][ s ],i});
	while(!q.empty())
	{
		int x=q.top().second;q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(auto i:G[x])
		{
			int y=i.first,w=i.second;
			if(dp[y][ s ]>dp[x][ s ]+w)
			{
				dp[y][ s ]=dp[x][ s ]+w;
				q.push({dp[y][ s ],y});
			}
		}
	}
}
int main()
{
int m,k;scanf("%d%d%d",&n,&m,&k);
for(int i=1,x,y,w;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
G[x].push_back({y,w});
G[y].push_back({x,w});
}
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=k;i++)
{
scanf("%d",&a[i]);
dp[a[i]][1<<(i-1)]=0;
}
for(int S=1;S<(1<<k);S++)//枚举给定点集的所有非空子集S
{
for(int s=S-1;s;s=S&(s-1))  // 枚举S的所有非空子集s
for(int i=1;i<=n;i++)
dp[i][ S ]=min(dp[i][ S ],dp[i][ s ]+dp[i][S^s]);
dijkstra(S);
}
printf("%d\n",dp[a[1]][(1<<k)-1]);
return 0;
}

</p>