问题2094--联网

2094: 联网

时间限制: 1 Sec  内存限制: 128 MB
提交: 11  解决: 11
[提交] [状态] [讨论版] [命题人:]

题目描述

已知该区域中的一组点，以及两点之间每条路线所需的电缆长度。请注意，在两个给定点之间可能存在许多路线。假设给定的可能路线（直接或间接）连接该区域中的每两个点，请设计网络，使每两个点之间都存在连接（直接或间接），并且使用的电缆总长度最小。

输入

输入由多个数据集组成，每个数据集都描述一个网络。数据集的第1行包含两个整数：第1个整数表示点数P （P ≤50），节点标号为1～P ；第2个整数表示点之间的路线数R 。以下R 行为点之间的路线，每条路线都包括3个整数：前两个整数为点标号，第3个整数为路线长度L （L ≤100）。数据集之间以空行分隔，输入仅有一个数字P （P =0）的数据集，表示输入结束。

输出

对于每个数据集，都单行输出所设计网络的电缆的最小总长度。

样例输入 Copy 

1 0
2 3
1  2 37
2 1 17
1 2 68

3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32

5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12

0

样例输出 Copy 

0
17
16
26

来源/分类

最小生成树 Prim算法 Kruskal算法 
[提交] [状态]