给定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
注意此代码没有考虑多组数据
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Node
{
int next,to,dis;
}edge[];
int q[],num,head[],dist[][],n,m,qq,f[(<<)][];
bool vis[];
void add(int u,int v,int dis)
{
num++;
edge[num].next=head[u];
head[u]=num;
edge[num].to=v;
edge[num].dis=dis;
}
void bfs(int x)
{int h,t,i;
q[]=x;
h=;t=;
dist[x][x]=;
memset(vis,,sizeof(vis));
while (h<t)
{
h++;
int u=q[h];
vis[u]=;
for (i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if (dist[x][v]>dist[x][u]+edge[i].dis)
{
dist[x][v]=dist[x][u]+edge[i].dis;
if (vis[v]==)
{
t++;
q[t]=v;
vis[v]=;
}
}
}
}
}
int main()
{int i,j,x,u,v,c,l;
cin>>n>>m>>qq;
memset(dist,/,sizeof(dist));
for (i=;i<=n+m;i++)
{
scanf("%d",&x);
add(,i,x);add(i,,x);
}
for (i=;i<=qq;i++)
{
scanf("%d%d%d",&u,&v,&c);
add(u,v,c);add(v,u,c);
}
for (i=;i<=n+m;i++)
bfs(i);
memset(f,/,sizeof(f));
for (i=;i<=n;i++)
{
for (j=;j<=n+m;j++)
{
f[<<i][j]=dist[i][j];
}
}
for (i=;i<=n+m;i++)
{
f[][i]=;
}
for (int sta=;sta<(<<(n+));sta++) if (sta&(sta-))
{
for (int i=;i<=n+m;i++)
for (int sub=sta;sub;sub=(sub-)&sta)
if (f[sta][i]>f[sub][i]+f[sta^sub][i])
f[sta][i]=f[sub][i]+f[sta^sub][i];
for (int i=;i<=n+m;i++)
for (int j=;j<=n+m;j++)
if (f[sta][i]>f[sta][j]+dist[j][i])
f[sta][i]=f[sta][j]+dist[j][i];
}
cout<<f[(<<n+)-][];
}
