最小斯坦纳树代码

#include<bits/stdc++.h>

using namespace std;

const int N = 103, M = 503, SZ = (1<<10)+3;

int n,m,k,p[13];
int ecnt, hd[N], nt[M*2+1], vr[M*2+1], w[M*2+1];
void ad(int u, int v, int w_) { nt[++ecnt] = hd[u], hd[u] = ecnt; vr[ecnt] = v, w[ecnt] = w_;}

int dp[N][SZ];

int vis[N];
priority_queue<pair<int, int> > q;
void dij(int S) {
	memset(vis, 0, sizeof vis);
	while(!q.empty())
	{
		int x = q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		for(int i=hd[x]; i; i=nt[i]) {
			int y = vr[i];
			if(dp[y][S] > dp[x][S] + w[i]) {
				dp[y][S] = dp[x][S] + w[i];
				q.push(make_pair(-dp[y][S], y));
			}
		}
	}
}

int main() {
	memset(dp, 0x3f, sizeof dp);
	
	scanf("%d%d%d", &n, &m, &k);
	for(int i=1; i<=m; ++i) {
		int x,y,z; scanf("%d%d%d", &x, &y, &z); ad(x,y,z); ad(y,x,z);
	}
	for(int i=1; i<=k; ++i) {
		scanf("%d", &p[i]);
		dp[p[i]][1<<(i-1)] = 0;
	}
	for(int S=1; S<(1<<k); ++S) {
		for(int i=1; i<=n; ++i) {
			for(int subs = (S-1)&S; subs; subs = (subs-1)&S)
				dp[i][S] = min(dp[i][S], dp[i][subs] + dp[i][S ^ subs]);
			if(dp[i][S] != 0x3f3f3f3f) q.push(make_pair(-dp[i][S], i));
		}
		dij(S);
	}
	cout << dp[p[1]][(1<<k)-1];
	return 0;
}