还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 45838 Accepted Submission(s): 20885
Problem Description
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5
#include<stdio.h>///prim
#include<string.h>
///建图——邻接矩阵
int vis[150][150];///邻接矩阵数组，将两城镇连接，并存储距离
int main()
{
int x,y,i,n,j,dis;
while(scanf("%d",&n)!=EOF)
{
if(!n)return 0;
for(i=0;i<n*(n-1)/2;i++)
{
scanf("%d%d%d",&x,&y,&dis);///x起点，y终点，w距离
vis[x][y]=dis;
vis[y][x]=dis;///当为无向图是加入此句，否则不加，公路是双向的，当然是无向图
}
int minn,mini,sum=0;///分别记录 minn为到达节点的最小长度，minid为最小的节点，sum为长度总和
bool seta[150];///标记是否走过
int lowcost[150];///到达某个节点所需要的最小距离
int mst[150];///记录父亲节点，形成树结构
memset(seta,false,sizeof(seta));
memset(mst,0,sizeof(mst));
memset(lowcost,0x3f,sizeof(lowcost));///储存每个点到现在已经构造好的生成树 也就是集合b的最短距离，memset按字节初始化0x7f是一个约等于最大值的数
///将其初始化的原因：表示不可取
mst[1]=0;///1号节点为根节点，入度为0，没有父亲节点
seta[1]=true;///标记1号节点走过
for(i=2;i<=n;i++)///初始化
{
mst[i]=1;
lowcost[i]=vis[1][i];///lowcos的初始化第i个值，等于从1连接到i的距离
}
for(i=2;i<=n;i++)///每次循环就新到达一个点，总共遍历n-1个点
{
minn=0x7fffffff;///初始化长度最小值
mini=0;///初始化到达长度最小的节点
for(j=1;j<=n;j++)///第一次遍历，查找一个能到达的节点中距离最短的
{
if(!seta[j]&&lowcost[j]<minn)
{
minn=lowcost[j];
mini=j;
}
}///记录下来
if(minn==0x7fffffff)return -1;
sum+=minn;///求和
seta[mini]=true;///标记
for(j=1;j<=n;j++)///第二次遍历，在走了上一个点的基础上，更新所有未走的点的最短距离
{
if(!seta[j]&&vis[mini][j]<lowcost[j])
{
lowcost[j]=vis[mini][j];
mst[j]=mini;///更新父亲节点
}
}
}
printf("%d
",sum);
}
}