1420-奇妙之旅


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:1 提交数:1 难度:4


题目描述:

终于有一个盼望已久的假期!立马拿出地图,标出最想去的n个景点,以及两个景点之间的距离dij,为了节省时间,我们希望在最短的时间内看遍所有的景点,而且同一个景点只经过一次。怎么计划行程,才能在最短的时间内不重复地旅游完所有景点回到家呢?


输入描述:

第一行是一个整型数C(C<100)表示共有C组测试数据。
每组测试数据第一行输入景点数n和景点之间的边数m(1<=n<=50,1<=m<=2500)。
接下来有m行,每行输入3个数,代表两个景点序号u、v及两景点之间的距离w(1<=u,v <=50, 1<=w <=100)。

输出描述:

对于每一组输入,输出满足条件的最短距离。
每组的输出占一行。

样例输入:

2
5 9
1 2 3
1 4 8
1 5 9
2 3 3
2 4 10
2 5 5
3 4 4
3 5 3
4 5 20
4 6
1 2 10
1 3 12
1 4 4
2 3 5
2 4 8
3 4 6

样例输出:

23
25

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!