思路：虚拟一个0号节点，将每个点建一条到0号节点的边，权值为挖井需要的价值。并要保证0号节点同另外n个寺庙一样被选择即可。
然后就是求斯坦纳树了。
#include<map> #include<set> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define Maxn 1310 #define Maxm 100010 #define LL __int64 #define Abs(x) ((x)>0?(x):(-x)) #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define inf 0x3f3f3f3f #define Mod 1000000007 using namespace std; int dp[Maxn][1<<7],dis[Maxn][Maxn],vi[Maxn],head[Maxn],e,n,m,p; struct Edge{ int u,v,val,next; }edge[Maxn*10]; void init() { memset(dis,38,sizeof(dis)); memset(dp,38,sizeof(dp)); memset(vi,0,sizeof(vi)); memset(head,-1,sizeof(head)); e=0; } void add(int u,int v,int val) { edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++; edge[e].u=v,edge[e].v=u,edge[e].val=val,edge[e].next=head[v],head[v]=e++; } void spfa() { int i,v,now,j; for(i=0;i<=n+m;i++){ queue<int> q; dis[i][i]=0; q.push(i); while(!q.empty()){ now=q.front(); q.pop(); vi[now]=0; for(j=head[now];j!=-1;j=edge[j].next){ v=edge[j].v; if(v==now) continue; if(dis[i][v]>dis[i][now]+edge[j].val){ dis[i][v]=dis[i][now]+edge[j].val; if(!vi[v]){ q.push(v); vi[v]=1; } } } } } } int solve() { int i,j,k; spfa(); int x=n+m; for(i=0;i<=n;i++){ for(j=0;j<=x;j++){ dp[j][1<<i]=dis[i][j]; } } int N=1<<(n+1); N--; for(i=1;i<=N;i++){ if(!(i&(i-1))) continue; for(j=0;j<=x;j++){ dp[j][i]=inf; for(k=i;k;k=(k-1)&i){ dp[j][i]=min(dp[j][i],dp[j][k]+dp[j][i-k]); } } for(j=0;j<=x;j++){ for(k=0;k<=x;k++){ dp[j][i]=min(dp[j][i],dp[k][i]+dis[k][j]); } } } return dp[0][N]; } int main() { int i,j,u,v,val; while(scanf("%d%d%d",&n,&m,&p)!=EOF){ init(); for(i=1;i<=n+m;i++){ scanf("%d",&val); add(0,i,val); } for(i=1;i<=p;i++){ scanf("%d%d%d",&u,&v,&val); add(u,v,val); } printf("%d ",solve()); } return 0; }