题意：若两个QS之间要想连网，除了它们间网线的费用外，两者都要买适配器，
求使所有的QS都能连网的最小费用
分析：这个除了边的权值外，顶点也有权值，因此要想求最小价值，必须算边及顶点的权值和
#include<cstdio>
#include<algorithm>
using namespace std;
int f[1010],n,m;
struct stu
{
int a,b,c;
}t[500100];
int cmp(struct stu x,struct stu y)
{
return x.c<y.c;
}
int find(int x)
{
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
}
int krus()
{
int i,k=0,s=0,x,y;
for(i=1;i<m;i++){
x=find(t[i].a);
y=find(t[i].b);
if(x!=y){
s+=t[i].c;
k++;
if(k==n-1)
break;
f[x]=y;
}
}
return s;
}
int main()
{
int T,i,j,a[1010],c,s=0;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(i=1;i<=n;i++){
f[i]=i;
scanf("%d",&a[i]);
}
m=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
scanf("%d",&c);
if(j<i){
t[m].a=i;
t[m].b=j;
t[m++].c=c+a[i]+a[j]; //计算边和顶点的权值和
}
}
sort(t+1,t+m,cmp);
s=krus();
printf("%d\n",s);
}
return 0;
}