首页 > 试题广场 >

旅行计划

[编程题]旅行计划
  • 热度指数：52 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

小美和小团计划去邻国旅行。邻国有N座城市，城市间由N-1条双向道路连通，且保证从任意城市出发，沿着这些道路可以到达其它任意城市。小美和小团可以从任意城市出发，沿着城市间的道路，以任意顺序游览每座城市，并且可以在任意城市结束旅行。那么，小美和小团想知道，他们至少要在道路上行驶多少距离，才能保证游历每座城市。


输入描述:
第一行输入一个整数T（1<=T<=10），表示数据组数。
对于每组数据，第一行输入一个整数N（1<=N<=10^5）；
接下来N-1行，每行输入三个由空格隔开的整数X、Y和L（1<=X,Y<=N、1<=L<=10^4），表示第X座城市和第Y座城市间有一条长为L的双向道路。


输出描述:
每组数据输出占一行，输出一个整数，表示游历每座城市至少要在道路上行驶的距离。
示例1

输入

1
5
1 2 1
1 3 4
3 4 2
3 5 3

输出

12

说明

小美和小团可以从第2座城市出发，行驶1的距离到达第1座城市，再行驶4的距离到大第3座城市，接着行驶2的距离到达第4座城市，最后行驶2+3=5的距离到达第5座城市。
算法知识视频讲解
添加回答
yosoro25252头像 yosoro25252
转化成无根树最长路径
发表于 2021-05-01 03:51:49 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 美团 前端工程师 算法工程师 2021 大数据开发工程师 Java工程师
上传者：小小
难度：
1条回答 1359浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号