1066. 新年趣事之游戏

时间限制 1000 ms
内存限制 128 MB

题目描述

  xiaomengxian的哥哥是一个游戏迷,他喜欢研究各种游戏。这天,xiaomengxian到他家玩,他便拿出了自己最近正在研究的一个游戏给xiaomengxian看。这个游戏是这样的:一个国家有N个城市,有些城市之间可以建设铁路,并且不同城市之间建设铁路的费用各不相同。问如何用最小的费用,使整个国家的各个城市之间能够互相到达。另外,铁路是双向的。xiaomengxian心想,这不是太简单了吗?这就是经典的MST问题。他的哥哥说,这个当然不算什么。关键是它还要求费用第二小的方案,这真是让人伤脑筋。xiaomengxian想了很久,也没有想出来,你能帮助他吗?
  费用第二小的方案的定义为:与费用最小的方案不完全相同,且费用值除费用最小的方案外最小。

输入数据

  第一行两个数 $N\ (2\le N\le 500),M,$ 分别表示国家的城市数和可以修建铁路的城市有多少对。
  接下来 $M$ 行,每行三个正整数 $A_i, B_i, C_i,$ 表示城市 $A_i$ 和 $B_i$ 之间可以修建铁路,费用为 $C_i$ 。

输出数据

  第一行:”Cost: “+一个整数,表示最小费用。(若不存在,输出 $-1)$
  第二行:”Cost: “+一个整数,表示第二小费用。(若不存在,输出 $-1)$

样例输入

4 6
1 2 2
2 3 2
3 4 2
4 1 2
1 3 1
2 4 1

样例输出

Cost: 4
Cost: 4

样例说明

Sample input #2
3 2
1 2 2
2 3 2

Sample output #2
Cost: 4
Cost: -1

题目信息

未提交
未通过无法查看
未通过无法查看