题意

给定n个点，m条双向边的图。其中有k个点是重要的。每条边都有一定的长度。
现在要你选定一些边来构成一个图，要使得k个重要的点相互连通，求边的长度和的最小值。

题解

标准的斯坦纳最小树模型
据说是NP问题，没有多项式解法
解法是状压DP
考虑到这种东西，最优情况肯定是一棵树
$f[i][j]$
表示连通性为i，以j为根的最小花费
递推式有两个
枚举子集转移$f[i][j]=min(f[l][j]+f[lxori][j])$
同层转移:$f[i][j]=min(f[i][k]+g[k][i]$
g是最短路
下面一个可以用dij优化
然后就可以了
CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
typedef long long LL;
const LL N=100005;
typedef pair<LL,int> PI;
LL n,k,m;
LL f[33][N];
struct qq
{LL x,y,z,last;
}e[N*5];LL num,last[N];
void init (LL x,LL y,LL z)
{num++;e[num].x=x;e[num].y=y;e[num].z=z;e[num].last=last[x];last[x]=num;
}
priority_queue<PI,vector<PI>,greater<PI> > q;
bool vis[33][N];
int main()
{memset(vis,false,sizeof(vis));num=0;memset(last,-1,sizeof(last));memset(f,63,sizeof(f));scanf("%lld%lld%lld",&n,&k,&m);for (LL u=0;u<k;u++){LL x;scanf("%lld",&x);f[1<<u][x]=0;}for (LL u=1;u<=m;u++){LL x,y,z;scanf("%lld%lld%lld",&x,&y,&z);init(x,y,z);init(y,x,z);}for (LL u=1;u<(1<<k);u++){for (LL i=u;i!=0;i=u&(i-1))for (LL j=1;j<=n;j++)f[u][j]=min(f[u][j],f[u^i][j]+f[i][j]);for (LL i=1;i<=n;i++) q.push(make_pair(f[u][i],i));while (!q.empty()){LL x=q.top().first,xx=q.top().second;q.pop();//printf("YES:%lld %lld\n",x,xx);if (vis[u][xx]) continue;vis[u][xx]=true;for (LL i=last[xx];i!=-1;i=e[i].last){LL y=e[i].y;if (f[u][y]>f[u][xx]+e[i].z){//printf("YES:%lld %lld %lld\n",y,xx,f[u][xx]);f[u][y]=f[u][xx]+e[i].z;// printf("%lld %lld %lld\n",u,y,f[u][y]);q.push(make_pair(f[u][y],y));}}}}LL ans=(1LL<<62);for  (LL u=1;u<=n;u++) ans=min(ans,f[(1<<k)-1][u]);printf("%lld\n",ans);return 0;
}
?