嘎唔！~又一次POJ过了HDU错了。。。不禁让我想起前两天的的Is it a tree? orz。。这次竟然错在HDU一定要是多组数据输入输出！（无力吐槽TT）。。题目很简单，炒鸡水！
题意：
告诉你每个村庄之间的距离，和几组已经联通的村庄，求使所有村庄联通所要建的道路的最短距离。
很简单，用最小生成树的Prim算法，相当于邻接矩阵已知，把已联通的村庄之间的距离改为零即可。
附上AC代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define infinity 1000001
#include<iostream>
#include<algorithm>
using namespace std;
int G[][];
int lowcost[];
int used[];
int prim(int vcount)
{
int sum=;
int i,j,k;
int min;
for (i=; i<vcount; i++)
{
lowcost[i]=G[][i];
used[i]=;
}
used[]=;
for (i=; i<=vcount-; i++)
{
j=;
min = infinity;
for (k=; k<vcount; k++)
if ((!used[k])&&(lowcost[k]<min))
{
min = lowcost[k];
j=k;
}
used[j]=;
sum+=min;
for (k=; k<vcount; k++)
if (!used[k]&&(G[j][k]<lowcost[k]))
{
lowcost[k]=G[j][k];
}
}
return sum;
}
int main()
{
int i,j;
int sum,n,q,a,b;
while(scanf("%d",&n)!=EOF)
{
for(i=; i<n; i++)
{
for(j=; j<n; j++)
{
scanf("%d",&G[i][j]);
}
}
scanf("%d",&q);
for(i=; i<q; i++)
{
scanf("%d%d",&a,&b);
G[a-][b-]=G[b-][a-]=;
}
sum=prim(n);
printf("%d\n",sum);
}
return ;
}
————Anonymous.PJQ