斯坦纳树
给定一个权值网络，求包含k个点的点集，使其相互连通的最小权值
时间复杂度： $ O(n \cdot 3^k +mlogm \cdot 2^k) $
cpp
void solve(){
int n,m,k;
cin>>n>>m>>k;
vector<PII> adj[n];
for(int i=0;i<m;i++){
int u,v,c;
cin>>u>>v>>c;
u--,v--;
adj[u].emplace_back(v,c);
adj[v].emplace_back(u,c);
}
vector<vector<int>> dp(1<<k,vector<int>(n,INF));
vector<int> pos(k);
for(int i=0;i<k;i++)cin>>pos[i],pos[i]--;
for(int i=0;i<k;i++)dp[1<<i][pos[i]]=0;
for(int s=0;s<1<<k;s++){
for(int t=s;t;t=(t-1)&s){
for(int i=0;i<n;i++)dp[s][i]=min(dp[s][i],dp[t][i]+dp[s^t][i]);
}
priority_queue<PII,vector<PII>,greater<PII>> q;
for(int i=0;i<n;i++){
if(dp[s][i]!=INF)q.emplace(dp[s][i],i);
}
while(!q.empty()){
auto [d,u]=q.top();
q.pop();
if(dp[s][u]!=d)continue;
for(auto [v,c]:adj[u]){
if(dp[s][v]>dp[s][u]+c){
dp[s][v]=dp[s][u]+c;
q.emplace(dp[s][v],v);
}
}
}
}
int ans=INF;
for(int i=0;i<n;i++){
ans=min(ans,dp[(1<<k)-1][i]);
}
cout<<ans<<"\n";
}