斯坦纳树
定义：
最小斯坦纳树，就是花费最少的代价，联通给定的 \(k\) 个关键点。
感觉有点像迪杰斯特拉，但是又不太一样。
引入：
用一道例题引入：
[模板] 最小斯坦纳树
参考：ix35题解
这个问题可以用 状压 \(DP\) 来解决，发现一个结论：
答案的子图一定是树
证明：如果答案存在环，则删去环上任意一条边，代价变小。
我们为这颗树钦定一个树根，设 \(dp[i][S]\) 表示以 \(i\) 为根的一棵树，包含集合 \(S\) 中所有点的最小代价。
考虑转移：一棵以 \(i\) 为根的树有两种情况：
- \(i\) 的度数等于 \(1\).
- \(i\) 的度数大于 \(1\).
第一种： 枚举树上与 \(i\) 相邻的点 \(j\):
\[dp[j][S]+w[j][i] \rightarrow dp[i][S] \]第二种：划分成几个子树考虑：
\[dp[i][T]+dp[i][S-T] \rightarrow dp[i][S] (T \in S) \]这里的转移顺序，可以理解成一个类似背包的 \(DP\) ，与 \(i\) 相邻的点是一个个出现的，每次多合并上一个点，所以按 \(S\) 升序枚举即可。
具体实现过程：
第一种： 考虑到最短路模型的三角形不等式( \(dij\) ) ,对于每一个 \(S\) ，将图做一次松弛操作即可。
第二种： 枚举子集，时间复杂度为 \(O(n \time 3^k)\)
#include<bits/stdc++.h>
using namespace std;
#define mk make_pair
#define pii pair<int,int>
const int N=1e3+5;
int n,m,k;
int nxt[N],edge[N],tot,ver[N],head[N];
int vis[N],p[N];
int dp[N][4005];
priority_queue<pii > q;
void add(int x,int y,int z){
ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; edge[tot]=z;
}
void dijkstra(int s){
memset(vis,0,sizeof(vis));
while(!q.empty()){
pii a=q.top(); q.pop();
if(vis[a.second]) continue;
vis[a.second]=1;
for(int i=head[a.second];i;i=nxt[i]){
int y=ver[i],z=edge[i];
if(dp[y][s]>dp[a.second][s]+z){
dp[y][s]=dp[a.second][s]+z;
q.push(mk(-dp[y][s],y));
}
}
}
}
int main(){
cin>>n>>m>>k;
memset(dp,0x3f3f3f3f,sizeof(dp));
for(int i=1,x,y,z;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
for(int i=1;i<=k;i++) scanf("%d",&p[i]),dp[p[i]][1<<(i-1)]=0;
//对应点对应S里的标号
for(int s=1;s<(1<<k);s++){//枚举每个点是否选择
for(int i=1;i<=n;i++){
for(int subs=s&(s-1);subs;subs=s&(subs-1))
dp[i][s]=min(dp[i][s],dp[i][subs]+dp[i][s^subs]);
//s&(s-1) 表示
if(dp[i][s]!=0x3f3f3f3f) q.push(mk(-dp[i][s],i));
//枚举每个点作为根的情况
}
dijkstra(s);
}
printf("%d\n",dp[p[1]][(1<<k)-1]);
system("pause");
return 0;
}