UOJ Logo 蜗牛编程训练题库

JZOJ

#309. 【poj1734】Sightseeing Trip

Statistics
时间限制:1s    空间限制:256MB    输入文件:TRIP.in    输出文件:TRIP.out
当前24小时内您还剩30次提交本题的机会

题目描述

给定一张无向图,求图中一个至少包含3个点的环,环上的节点不重复,并且环上的边的长度和最小。该问题被称为无向图的最小环问题。在本题中,你需要输出最小环的方案,若最小环不唯一,输出任意一个均可。若无解,输出$No$ $solution.$。

输入格式

第一行包含两个正整数$n$和$m$,分别表示图中有$n$个节点$m$条边。接下来$m$行每行三个正整数$x$,$y$,$v$描述一条$x$与$y$之间权值为$v$的无向边。

输出格式

输出仅一行,包含$No$ $solution.$或若干个空格隔开的正整数,以描述所求的最小环。

若有多种方案,仅要求输出任意一种。对于任意一种方案,请按环上的遍历顺序输出编号。

样例

Input

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

Output

1 3 5 2

数据规模

对于$100\%$的数据,保证$1<=n<=100$,$1<=m<=10000$,$1<=vi<=500$。

题目来源

$POJ1734$。

特别注意

本题数据已经可以spj,于2019年9月3日

Solutions

标题 发表者 发表日期
None