zoj1586:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1586
题目大意：最小生成树，不只算两点之间的费用，还要算点的费用，并不是个点只算一次费用，而是每出现一次算一次。
题解：其实只需要在算距离时，把两点的距离加入其中在排序就行了。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define INF 100000000
using namespace std;
int n,cas;
int g[][];
int lowcost[];
int num[];
void prim(int v0){
int sum=;
for(int i=;i<=n;i++){
lowcost[i]=g[v0][i];
}
lowcost[v0]=-;
for(int i=;i<n;i++){
int min=INF;
int v=-;
for(int j=;j<=n;j++){
if(lowcost[j]!=-&&lowcost[j]<min){
min=lowcost[j];
v=j;
}
}
if(v!=-){
sum+=lowcost[v];
lowcost[v]=-;
for(int k=;k<=n;k++){
if(lowcost[k]!=-&&g[v][k]<lowcost[k]){
lowcost[k]=g[v][k];
}
}
}
}
printf("%d\n",sum);
}
int main(){
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
memset(g,,sizeof(g));
for(int i=;i<=n;i++)
scanf("%d",&num[i]);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
scanf("%d",&g[i][j]);
g[i][j]+=num[i]+num[j];
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(i==j)g[i][j]=;
else if(g[i][j]==)g[i][j]=INF;
}
prim();
}
}