给定N个寺庙，和M个另外的地方。
然后给定点权，表示在这个点挖水井需要的代价。
再给定边权，为建造无向边i，j的代价。
然后求怎样弄最小的代价使得前N个点，就是寺庙都能从挖的井里得到水。
输入输出格式
输入格式：
第1行：三个整数N，M，Q（Q的含义下面有解释）
第2行：共N+M个整数，第i个数表示在编号为i的地方安装适配器费用Ai
第3～Q+2行：每行三个整数U，V，C，表示编号为U，V间连接网线的费用为C
输出格式：
共1行，1个整数，表示使所有机房连上网的费用最小值。
输入输出样例
输入样例#1：
3 1 3 1 2 3 4 1 4 2 2 4 2 3 4 4
输出样例#1：
6
输入样例#2：
4 1 4 5 5 5 5 1 1 5 1 2 5 1 3 5 1 4 5 1
输出样例#2：
5
说明
样例解释：
对于样例1：直接在每个机房安装适配器，开销最小，为1+2+3=6。
对于样例2：在唯一一个非机房的教室安装适配器，并从此处接网线到各个机房，开销最小，为1+1+1+1+1=5。
数据规模：
20%的数据有N=1；
另20%的数据有N=2；
另20%的数据有N=3；
100%的数据有1<=N<=5，1<=M<=1000，M<=Q<=5000，1<=A，C<=10000。
斯坦纳树的应用：
与模板相比，多了点权的设定，即一个联通块要有一个点权
方法很简单，设一个0节点，i点权值为x则加边(0,i,x)，求部分点最小生成树(斯坦纳树)
斯坦纳树的概念和实现方法：http://blog.csdn.net/gzh1992n/article/details/9119543
注意此代码没有考虑多组数据
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 struct Node 7 { 8 int next,to,dis; 9 }edge[200001]; 10 int q[100001],num,head[100001],dist[2001][2001],n,m,qq,f[(1<<7)][2001]; 11 bool vis[100001]; 12 void add(int u,int v,int dis) 13 { 14 num++; 15 edge[num].next=head[u]; 16 head[u]=num; 17 edge[num].to=v; 18 edge[num].dis=dis; 19 } 20 void bfs(int x) 21 {int h,t,i; 22 q[1]=x; 23 h=0;t=1; 24 dist[x][x]=0; 25 memset(vis,0,sizeof(vis)); 26 while (h<t) 27 { 28 h++; 29 int u=q[h]; 30 vis[u]=0; 31 for (i=head[u];i;i=edge[i].next) 32 { 33 int v=edge[i].to; 34 if (dist[x][v]>dist[x][u]+edge[i].dis) 35 { 36 dist[x][v]=dist[x][u]+edge[i].dis; 37 if (vis[v]==0) 38 { 39 t++; 40 q[t]=v; 41 vis[v]=1; 42 } 43 } 44 } 45 } 46 } 47 int main() 48 {int i,j,x,u,v,c,l; 49 cin>>n>>m>>qq; 50 memset(dist,127/3,sizeof(dist)); 51 for (i=1;i<=n+m;i++) 52 { 53 scanf("%d",&x); 54 add(0,i,x);add(i,0,x); 55 } 56 for (i=1;i<=qq;i++) 57 { 58 scanf("%d%d%d",&u,&v,&c); 59 add(u,v,c);add(v,u,c); 60 } 61 for (i=0;i<=n+m;i++) 62 bfs(i); 63 memset(f,127/3,sizeof(f)); 64 for (i=0;i<=n;i++) 65 { 66 for (j=0;j<=n+m;j++) 67 { 68 f[1<<i][j]=dist[i][j]; 69 } 70 } 71 for (i=0;i<=n+m;i++) 72 { 73 f[0][i]=0; 74 } 75 for (int sta=1;sta<(1<<(n+1));sta++) if (sta&(sta-1)) 76 { 77 for (int i=0;i<=n+m;i++) 78 for (int sub=sta;sub;sub=(sub-1)&sta) 79 if (f[sta][i]>f[sub][i]+f[sta^sub][i]) 80 f[sta][i]=f[sub][i]+f[sta^sub][i]; 81 for (int i=0;i<=n+m;i++) 82 for (int j=0;j<=n+m;j++) 83 if (f[sta][i]>f[sta][j]+dist[j][i]) 84 f[sta][i]=f[sta][j]+dist[j][i]; 85 } 86 cout<<f[(1<<n+1)-1][0]; 87 }