1017_还是畅通工程
2019-11-14 09:49:20
供稿：网友
// 1017_还是畅通工程.cpp : 定义控制台应用程序的入口点。//题目1017：还是畅通工程//时间限制：1 秒内存限制：32 兆特殊判题：否提交：6085解决：3025//题目描述：//某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。//输入：//测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。//当N为0时，输入结束，该用例不被处理。//输出：//对每个测试用例，在1行里输出最小的公路总长度。//样例输入：//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//样例输出：//3//5//来源：//2006年浙江大学计算机及软件工程研究生机试真题#include "stdafx.h"#include "stdio.h"#include "iostream"#include "limits.h"#include "string.h"using namespace std;#define MAX 110int N;int dist[MAX][MAX],lowcost[MAX],visit[MAX];int main(){ while(cin>>N && N){ int x,y,z; for(int i = 0;i<N*(N-1)/2;i++){ cin>>x>>y>>z; dist[x][y] = dist[y][x] = z; } memset(visit,0,sizeof(visit)); for(int i = 2;i<=N;i++) lowcost[i] = INT_MAX; int start = 1; //每次加入集合的点（第一个点是1） int min_dist = 0; //累加的距离 int count = 1; //已经加入集合的点的个数 int cursor = start; //记录当前距集合最小距离的位置 visit[start] = 1; while(count<N){ for(int i =1;i<=N;i++){ if(!visit[i]){ lowcost[i] = min(lowcost[i],dist[start][i]); cursor = lowcost[i]<lowcost[cursor]?i:cursor; } } start = cursor; visit[start] = 1; count++; min_dist += lowcost[start]; lowcost[cursor] = INT_MAX; } cout<<min_dist<<endl; } return 0;}/*1.INT_MAX*/
