最小斯坦纳树

题意：

给出一张 (n) 个点的无向图，其中 (k) 个点是关键点，问可以将所有关键点相连的最小网络是多大。

Solution：

考虑 DP ，(f_{i,S}) 表示做到 (i) 号点，包含关键点的集合为 (S) ，考虑转移有两种方式：

1. (f_{i,S|T} = f_{i,S} + f_{i,T})
2. (f_{x,S} = f_{y,S} + w(y,x))

第一个枚举子集，第二个 spfa 或 dij 转移。

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int N=110;
const int M=1010;
const int SZ=1e5;
const int LIM=1030;
const int INF=1e9+7;
int n,m,k,tot,last[N],f[N][LIM],ans;
bool bz[N];
int st,en;
int q[SZ+5];
struct edge{
	int st,en,v,next;
}E[M];
void add(int x,int y,int z){
	E[++tot]=(edge){x,y,z,last[x]};
	last[x]=tot;
}
void spfa(int S){
	st=en=0;
	fo(i,1,n)
		if(f[i][S]<f[0][0])q[++en]=i,bz[i]=1;
	while(st!=en){
		int x=q[++st];
		for(int p=last[x];p;p=E[p].next){
			int y=E[p].en;
			if(f[y][S]>f[x][S] + E[p].v){
				f[y][S]=f[x][S] + E[p].v;
				if(!bz[y]){
					q[++en]=y;
					bz[y]=1;
				}
			}
		}
		bz[x]=0;
	}
}
int main(){
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	fo(i,1,m){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}
	memset(f,127,sizeof(f));
	fo(i,1,k){
		int x;
		scanf("%d",&x);
		f[x][1<<i-1]=0;
	}
	fo(i,1,n)f[i][0]=0;
	int lim=(1<<k)-1;
	fo(S,1,lim){
		fo(i,1,n){
			for(int T=S&(S-1);T;T=S&(T-1)){
				f[i][S]=min(f[i][S] ,f[i][T] + f[i][S^T]);
			}
		}
		spfa(S);
	}
	ans=INF;
	fo(i,1,n)ans=min(ans ,f[i][lim]);
	printf("%d
",ans);

	return 0;
}