这道题目没有做出来，代码写好之后一直没有AC，本以为做了这么多最小生成树的题目，这道题一定没问题的，结果很遗憾，没有注意细节问题：
首先，如何处理已经建好的路？已经建好的路说明这两个点是连通的，只要把他们间距设为0就好了。
其次，注意循环的控制，我把第一个for中的i=1写成i=0了。
Problem : 1102 ( Constructing Roads ) Judge Status : AcceptedRunId : 5913541 Language : C Author : qq1203456195Code Render Status : Rendered By HDOJ C Code Render Version 0.01 Beta
//最小生成树
#include<stdio.h>
#define N 1005
#define MAX 9999
int map[N][N],visited[N],close[N],n,q,a,b;
int main()
{
int i,j,nxt,len,nid,flag=
1;
while(~scanf(
"%d",&
n))
{
for(i=
0;i<n;i++
)
{
visited[i]=
0;
for(j=
0;j<n;j++
)
scanf("%d",&
map[i][j]);
}
scanf("%d",&
q);
for(i=
0;i<q;i++
)
{
scanf("%d%d",&a,&b);
//ab in tree
map[a-
1][b-
1]=map[b-
1][a-
1]=
0;
}
visited[0]=
1;
for(j=
0;j<n;j++
)
close[j]=map[j][
0];
len=
0;
for(i=
1;i<n;i++
)
{
nxt=
MAX;
for(j=
0;j<n;j++
)
{
if(!visited[j]&&close[j]<
nxt)
{
nxt=
close[j];
nid=
j;
}
}
len+=
nxt;
visited[nid]=
1;
for(j=
0;j<n;j++
)
{
if(!visited[j]&&map[j][nid]<
close[j])
close[j]=
map[j][nid];
}
}
printf("%d\n",len);
}
return 0;
}
转载于:https://www.cnblogs.com/CheeseZH/archive/2012/05/08/2489824.html
相关资源：数据结构—成绩单生成器
