Python 最小生成树
本帖最后由 欧德奈瑞 于 2020-12-15 17:17 编辑7-1 村村相连
漳州市政府调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。市政府的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
输入格式:
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N(N<100)和两村庄间的公路数M；随后的M行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N、M为0时，输入结束，该用例不被处理。
输出格式:
对每个测试用例，在1行里输出最小的公路总长度，如果未能找到请输出"no found!"。
输入样例1:
在这里给出两组输入。例如：
3 3
1 2 10
1 3 20
2 3 40
4 6
1 2 10
1 3 40
1 4 10
2 3 30
2 4 20
3 4 50
0 0
输出样例1:
在这里给出相应的输出。例如：
30
50
输入样例2:
在这里给出两组输入。例如：
4 5
1 2 10
1 3 40
1 4 10
2 4 20
3 4 50
5 6
1 2 20
1 3 10
1 4 20
1 5 10
2 5 30
4 5 30
0 0
输出样例2:
在这里给出相应的输出。例如：
60
60
页:
[1]