odd doctor 已更新

路径规划

Time Limit
5s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
50.00%(1/2)
Description:

小Z没事的时候喜欢研究地图,有一天看着地图,他产生了一个疑惑。地图上有n个城市,现在小Z想给这n个城市之间造路,希望能让城市之间两两可达。小Z给出了m种供选择的道路,每种选择是一个三元组(u, v, w),代表给u城市和v城市之间建造一条长度为w的道路。小Z当然希望最终的道路总长越小越好,但同时他又很矛盾的希望所有选择的道路中最长的那条路越长越好,你能帮帮他吗?

Input:

第一行给出一个整数T(1<=T<=20),表示测试数据的数目。
每一组测试数据第一行包含两个正整数nm。(2<=n<=1001<=m<=10000)

接下来是m行数据,每行数据都是三个空格隔开的正整数u, v, w(1<=u,v<=n,1<=w<=10000)

保证至少存在一种方案,使得城市两两可达。

Output:

对于每组数据,输出一行用空格隔开的两个数,路径总长和所有路中最长的那条路的长度

Sample Input:
1
3 3
1 2 1
1 3 2
2 3 1
Sample Output:
2 1
Source:

hdu校赛


Submit