题意：给定一个无向图，求把重要节点联通的最小代价（重要节点<=5）

将指定点集合中的所有点连通，且边权总和最小的生成树称为最小斯坦纳树（Minimal Steiner Tree）

其实最小生成树是最小斯坦纳树的一种特殊情况，联通了图上所有节点

最小斯坦纳树可以用dp求解

令$f[i][j]$表示以$i$为根，指定集合中点的联通状态为$j$的最小总权值

转移分为两重

• 第一重：枚举当前状态的子集进行转移

  方程为：$f[i][j]=min(f[i][j],f[i][k]+f[i][j xor k])$

  枚举子集的技巧是：$for (k=j\&(j-1);k;k=j\&(k-1))$

• 第二重：在当前状态下对其进行松弛操作

  方程为:$f[i][j]=min(f[i][j],f[k][j]+cost)$

  在这一重只需对这一种状态进行松弛即可，因为其他状态会通过第一重转移更新

  松弛操作可以通过spfa实现（如果spfa又双叒叕被卡了请使用堆优化dijkstra）

相关题目：[JLOI2015]管道连接 [WC2008]游览计划

现在时限扩大了，加上点常数优化就可以AC了orzzzzz

~虽然我不会写fread~

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct node
{
	int to,nxt,dis;
}edge[N<<2];
struct P
{
	int x; ll d;
	inline friend bool operator < (P a,P b) {return a.d>b.d;}
};
int n,m,p,num,head[N];
ll f[N][32],inf,ans=1e18;
bool vis[N];
priority_queue<P>q;
inline int read()
{
	int x=0,w=1;
	char c=getchar();
	while (!isdigit(c)&&c!='-') c=getchar();
	if (c=='-') c=getchar(),w=-1;
	while (isdigit(c))
	{
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*w;
}
inline void add_edge(int from,int to,int dis)
{
	edge[++num]=(node){to,head[from],dis};
	head[from]=num;
}
inline void dijkstra(int S)
{
	memset(vis,0,sizeof(vis));
	while (!q.empty())
	{
		int u=q.top().x; q.pop();
		if (vis[u]) continue; vis[u]=1;
		for (reg int i=head[u];i;i=edge[i].nxt)
		{
			int v=edge[i].to,d=edge[i].dis;
			if (f[v][S]>f[u][S]+d)
			{
				f[v][S]=f[u][S]+d;
				q.push((P){v,f[v][S]});
			}
		}
	}
}
int main()
{
	n=read(),p=read(),m=read();
	memset(f,127/3,sizeof(f)); inf=f[0][0];
	for (reg int i=1;i<=p;i++) f[read()][1<<(i-1)]=0;
	for (reg int i=1;i<=m;i++)
	{
		int x=read(),y=read(),z=read();
		add_edge(x,y,z); add_edge(y,x,z);
	}
	for (reg int i=1;i<(1<<p);i++)
	{
		for (reg int k=1;k<=n;k++)
		{
		    for (reg int j=i&(i-1);j;j=i&(j-1))
		      f[k][i]=min(f[k][i],f[k][j]+f[k][i^j]);
		    if (f[k][i]<inf) q.push((P){k,f[k][i]});
		}
		dijkstra(i);
	}
	for (reg int i=1;i<=n;i++) ans=min(ans,f[i][(1<<p)-1]);
	printf("%lld\n",ans);
	return 0;
}

斯坦纳树板子。

根据题目，$k$ 只有 $5$，故而我们状压的时候就可以考虑把关键点状态加进去。

设 $dp_{i,j}$ 表示选择 $i$ 个边，关键点是否选择的二进制状态为 $j$，并且以 $i$ 为生成树的端点，保证关键点是联通的，最小权值是多少。

考虑两棵残血生成树，将他们合并，可以考虑松弛，这个操作形如用 $dp_{k,j}$ 去更新 $dp_{i,j}$，松弛操作显然可以最短路优化。

式子：$dp_{i,j}=\min(dp_{i,j},dp_{k,j}+w)$，$w$ 是边权。

还有一种情况，用 $j$ 的一个子集去更新 $dp_{i,j}$。

式子：$dp_{i,j}=\min(dp_{i,j},dp_{i,jj}+dp_{i,j xor jj})$，其中 $jj$ 是 $j$ 的子集。

枚举子集考虑用二进制。

另外，这个题貌似要卡常，最短路用 $dij$ 的话最好手写堆。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define pii pair<long long,int>
using namespace std;
int n,m,k,u,v,w,p[6];
long long dp[1<<6][200001];
bool vis[200001];
struct dui{
	int x;
	long long dis;
	inline friend bool operator <(const dui &a,const dui &b){
		return a.dis>b.dis;
	}
};
priority_queue<dui> qq;
vector<pair<int,int> > z[200001];
void dij(int x){
	memset(vis,0,sizeof(vis));
	while(qq.size()){
		dui info=qq.top();
		qq.pop();
		int f=info.x;
		if(vis[f])continue;
		vis[f]=true;
		for(auto zhc:z[f]){
			int u=zhc.first,w=zhc.second;
			if(dp[x][u]>dp[x][f]+w){
				dp[x][u]=dp[x][f]+w;
				qq.push((dui){u,dp[x][u]});
			}
		}
	}
}
inline int read(){int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;}void solve(){
	n=read(),k=read(),m=read();
	memset(dp,127/3,sizeof(dp));
	long long b=dp[0][0];
	for(short i=1;i<=k;i++){
		p[i]=read();
		dp[1<<i-1][p[i]]=0;
	}
	for(int i=1;i<=m;i++){
		u=read(),v=read(),w=read();
		z[u].push_back(make_pair(v,w));
		z[v].push_back(make_pair(u,w));
	}
	for(short mask=1;mask<(1<<k);mask++){
		for(int i=1;i<=n;i++){
			for(int mask2=mask&(mask-1);mask2;mask2=(mask2-1)&mask){
				dp[mask][i]=min(dp[mask][i],dp[mask2][i]+dp[mask^mask2][i]);
			}
			if(dp[mask][i]<b){
				qq.push((dui){i,dp[mask][i]});
			}
		}dij(mask);
	}
	long long ans=10000000000000;
	for(int i=1;i<=n;i++) ans=min(ans,dp[(1<<k)-1][i]);
	cout<<ans<<'\n';
}signed main(){solve();return 0;}