题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4006
用斯坦纳树求出所有关键点的各种连通情况的代价，把这个作为状压(压的是集合选择情况)的初值DP即可。
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #define pb push_back using namespace std; int rd() { int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return f?ret:-ret; } int const xn=1005,xm=6005,xxn=(1<<10)+5,inf=0x3f3f3f3f; int n,m,hd[xn],ct,to[xm],nxt[xm],w[xm],f[xn][xxn],g[xxn]; int c[15],bin[15],cnt; bool vis[xn]; queue<int>q; vector<int>v[15]; int Min(int x,int y){return x<y?x:y;} void add(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; w[ct]=z;} void spfa(int sta) { memset(vis,0,sizeof vis); for(int i=1;i<=n;i++)if(f[i][sta]<inf)q.push(i),vis[i]=1; while(q.size()) { int x=q.front(); q.pop(); vis[x]=0; for(int i=hd[x],u;i;i=nxt[i]) if(f[u=to[i]][sta]>f[x][sta]+w[i]) { f[u][sta]=f[x][sta]+w[i]; if(!vis[u])vis[u]=1,q.push(u); } } } int main() { bin[0]=1; for(int i=1;i<=10;i++)bin[i]=bin[i-1]*2; n=rd(); m=rd(); int K=rd(); for(int i=1,x,y,z;i<=m;i++) x=rd(),y=rd(),z=rd(),add(x,y,z),add(y,x,z); memset(f,0x3f,sizeof f); for(int i=1,cr,x;i<=K;i++) { cr=rd(); x=rd(); if(!c[cr])c[cr]=++cnt; v[c[cr]].pb(i); f[x][bin[i-1]]=0;//i! } int mx=bin[K]; for(int sta=1;sta<mx;sta++) { for(int i=1;i<=n;i++) for(int s=(sta&(sta-1));s;s=(sta&(s-1))) f[i][sta]=Min(f[i][sta],f[i][s]+f[i][sta^s]); spfa(sta); } memset(g,0x3f,sizeof g); mx=bin[cnt]; for(int sta=1;sta<mx;sta++) { int s=0; for(int j=1;j<=cnt;j++) if(sta&bin[j-1]){for(int k=0;k<v[j].size();k++)s|=bin[v[j][k]-1];} for(int j=1;j<=n;j++)g[sta]=Min(g[sta],f[j][s]); } for(int sta=1;sta<mx;sta++) for(int s=(sta&(sta-1));s;s=(sta&(s-1))) g[sta]=Min(g[sta],g[s]+g[sta^s]); printf("%d ",g[mx-1]); return 0; }