九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1017-九度Online Judge,用代码记录你的成长之路!

题目1017:还是畅通工程

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:8139

解决:4031

题目描述:
    某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
输入:

    测试输入包含若干测试用例。每个测试用例的第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年浙江大学计算机及软件工程研究生机试真题
答疑:
解题遇到问题?分享解题心得?讨论本题请访问:http://t.jobdu.com/thread-7741-1-1.html