/ TYWZ / 题库 /

卡丁车

卡丁车

【题目背景】
Ljt12138是TYWZOI著名的老司机,经常直播开卡丁车。这天,Ljt12138研究出了自制卡丁车地图的方法,于是他拿了一个模板,想自制一张神奇的卡丁车地图。
【题目描述】
整个模板是一个图,有n个节点,m条带权无向边(权值表示经过这条边所需时间),每条无向边连着两个节点。保证没有自环,且整张图是联通的。
Ljt12138想简化这张图,即在保证所有节点两两互相可达的情况下,去掉若干条边,使整张图的边权和最小。建好地图后,Ljt12138想以图中的某个点为起点,用尽量少的时间遍历一遍他建好的地图。
【输入格式】
第一行两个正整数,表示n,m。
接下来m行,每行三个整数ui,vi,wi,表示ui,vi间有一条边权为wi的边。
【输出格式】
两个正整数,表示最小的边权和以及最短的遍历时间,用空格隔开。
【样例输入】
3 3
1 2 1
1 3 2
2 3 3
【样例输出】
3 3
【数据范围】
对于 10%的数据,n<=10
对于 30%的数据,n<=1000
对于 100% 的数据,1<n<=100000,1<=m<=200000,1<=ui,vi<=n,0<wi<=10^6
所有wi互不相同

信息

ID
1033
难度
8
分类
(无)
标签
(无)
递交数
126
已通过
14
通过率
11%
上传者

相关