九度Online Judge

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

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

题目1414:旅游啦

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:279

解决:89

题目描述:
你们可曾计划过今年暑假的毕业旅行呢?当年阳仔毕业旅行时,本来预计去的10个城市,结果因为没做足准备,才去了5个城市,并且白浪费了很多大洋在一个城市周转。今年他为了弥补上回的缺憾,打算再一次周游旅行,并且这次他计划了50个城市!!!阿门!!!
你们也知道的,周游旅行需要大笔费用。因此,阳仔打算坐动车,并将所到城市都拍张照片留作纪念。暑假2个月时间并不是所有城市都有动车可以直达的,如果某个城市没有动车,那他只能放弃去那个城市了。另外,可以保证如果动车可以从A->B,那么这班动车也可以从B->A。请你帮阳仔算下,阳仔开始所在城市编号为0,要到达所有的其他可以到达的城市,这一波旅行的最短路程是多少?

输入:
输入有多组测试案例,每个测试案例为m+1行。
第一行输入一个整数m表示有m条线路,接下去的m行,每行输入3个整数表示动车线路的始发点和路程。(城市编号从0 开始到 49,注意,不是所有的城市都可能有线路可以到达,我们保证给出的数据可以构成连通图并且至少有一条线路包含0。并且保证图没有环、没有重边,实际上已被简化为一棵树。

输出:
对应每个测试案例,输出从0号城市出发,周游其他城市的最短旅游行程。

样例输入:
5
0 1 10
0 3 10
0 4 100
1 2 10
4 5 5
样例输出:
165
提示:
案例中出现6个城市,因此阳仔要访问其余5个城市的最短旅游路线是:0->1->2->1->0->3->0->4->5