求助 Python 最小生成树
本帖最后由 欧德奈瑞 于 2020-12-14 19:21 编辑7-1 村村相连
漳州市政府调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。市政府的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
输入格式:
有多组测试数据，每组数据请依次输入图中各顶点的值，每个顶点值以回车间隔，并以#作为输入结束符；再请依次输入图中每条边的两个顶点值，两个顶点值以空格作为间隔，每输入一组后进行换行，仍以#结束输入；最后一行为某顶点v。
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N(N<100)和两村庄间的公路数M；随后的M行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N、M为0时，输入结束，该用例不被处理。
输出格式:
对每个测试用例，在1行里输出最小的公路总长度，如果未能找到请输出"no found!"。
输入样例:
在这里给出两组输入。例如：
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
#
输出样例:
在这里给出相应的输出。例如：
30
50
页:
[1]