(lpj 1-5)Fence loop

(lpj 1-5)Fence loop

测试数据来自 nnu_contest/5c11e63be561762f53b33c30

Farmer John(以下简称FJ)的农场有一片由柱子和栅栏构成的牛圈。
两个柱子之间可以有一条栅栏连接,但一个柱子可以和多个其他的柱子用栅栏连接。
如果栅栏围成封闭的一圈就可以形成一个牛圈。
奶牛们喜欢在牛圈里绕圈散步。
由于设计不周,有的牛圈周长太短,住在那儿的奶牛向FJ抱怨散不了几步又回到起点了。
FJ决定接受民意,拆掉周长最小的那个小牛圈,就请你用计算机找出这个牛圈。
输入M+1行,第1行两个整数分别是柱子的数量N和栅栏的数量M。我们把这N个柱子的编号为1,2,3……N。
第2到M+1行,每行都是三个整数A,B,L,表示编号A的柱子和B的柱子之间有一条长L的栅栏连接。题目保证可以形成牛圈。2<=N<=100,1<=M<=3000,1<=L<=1000。
输出1个整数,表示周长最短的牛圈的周长。

测试样例:
输入:

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

输出:

11

解释:

1,2,4号柱子组成的牛圈周长最小,为11。


由LydiaCCC翻译的英文题面版:点击

信息

ID
1662
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者