问题 1042. -- 接水管

1042: 接水管

时间限制: 1 Sec  内存限制: 128 MB
提交: 9  解决: 3
[提交][状态][讨论版]

题目描述

你领到了一个铺设校园内自来水管道的任务。校园内有若干需要供水的点,每两个供水点可能存在多种铺设路径。对于每一种铺设路径,其成本是已知的。

任务要求最终铺设的管道保证任意两点可以直接或间接的联通,同时总成本最低。

输入

每个测试用例由多行组成,第一行是两个整数PRP代表供水点数(1<=P<=50),每个点都对应1P中的一个唯一编号。R代表可能的铺设路径数,路径数可能有非常多。接下有R行,每行格式如下:

节点A编号 节点B编号 路径成本

路径成本不超过100

测试用例之间有一空行分开。输入结束用P=0表示,注意没有R值。

输出

每个测试用例占用一行输出最低总成本。

样例输入

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

样例输出

0
17
16
26

提示

来源

[提交][状态]