Sol.P6192

Upd：开坑了，等会再补

Upd 2023/8/24：补完了！！

Upd：改了很多遍了，希望管理过审或明确帮忙指出一下到底哪行有问题qwq谢谢

题目传送门

前置知识：最小斯坦纳树

最小斯坦纳树可以理解为升级版的最小生成树。

首先给定图 \(G=(V,E)\),以及 \(V\) 的子集 \(U\)，\(U\) 中的点为终端节点。最小斯坦纳树即求包含所有终端节点的 \(G\) 的子树中用到边权总和最小的。

• 在最小斯坦纳树中，若所有顶点都为终端节点，这个问题就是最小生成树问题。

• 最小斯坦纳树已经被证明是 NP-Hard 问题，所以可能不存在高效算法

举个例子

如上图，已知其终端节点为 \(A,B,C,F\)，则其最小斯坦纳树如下：

思路：考虑状压DP

可以将 \(dp_{i,s}\) 看作

考虑以下两种转移方式:

• \(dp_{i,S}=dp_{i,T}+dp_{i,S-T} \quad \quad (T\subseteq S )\)

• \(dp_{i,S}=dp_{i,s}+w(i,j)\)

显然只需枚举 \(S\) 的子集 \(T\) 即可,然后发现可以用最短路跑一边，于是故解法为状压DP+最短路

代码如下：

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define LL long long
using namespace std;
inline int read();
void write(int x);
struct Edge{int to,next,dis;}edge[1010];
int n=read(),m=read(),k=read();
int head[1010],tree[1010],cnt;
int dp[1010][5010],vis[1010],key[1010];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
void add(int u,int v,int w){
	edge[++cnt].next=head[u],edge[cnt].to=v,edge[cnt].dis=w;
	head[u]=cnt,tree[cnt]=v; 
}
#define P pair<int,int>
void dijkstra(int s){
	memset(vis,0,sizeof(vis));
	while(!q.empty()){
		pair<int,int> p=q.top();
		q.pop();	
		if(vis[p.second]) continue;
		vis[p.second]=1;
		for(int i=head[p.second];i;i=edge[i].next){
			if(dp[tree[i]][s]>dp[p.second][s]+edge[i].dis){
				dp[tree[i]][s]=dp[p.second][s]+edge[i].dis;
				q.push(P(dp[tree[i]][s],tree[i]));
			}
		}
	}
}
void init(){
	int u,v,w;
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=m;i++){
		u=read(),v=read(),w=read();
		add(u,v,w);
		add(v,u,w);
	}
	for(int i=1;i<=k;i++){
		key[i]=read();
		dp[key[i]][1<<(i-1)]=0;
	}
}
int main(){
	//freopen("MST.in","r",stdin);
	//freopen("MST.out","w",stdout);
	init();
	for(int s=1;s<(1<<k);s++){
		for(int i=1;i<=n;i++){
			for(int j=s&(s-1);j;j=s&(j-1))dp[i][s]=min(dp[i][s],dp[i][j]+dp[i][s^j]);
			if(dp[i][s]!=0x3f) q.push(P(dp[i][s],i));	
		}
		dijkstra(s);
	}
	write(dp[key[1]][(1<<k)-1]); 
	return 0;
}
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-'0';
		ch=getchar();
	}
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
    return;
}