CHDOJ
首页
题库
题单
比赛
评测
用户
讨论
帮助
工具
云剪贴板
树图画板
代码对比
登录
注册
4055: Sightseeing Trip
时间限制:1000 ms
内存限制:256 MB
上传者:
提交:36
通过:10
提交
提交记录
讨论
统计
题目描述
给定一张无向图,求图中一个至少包含 $3$ 个点的环,环上的节点不重复,并且环上的边的长度之和最小。
该问题称为无向图的最小环问题。在本题中,你需要输出最小环的方案,若最小环不唯一,输出任意一个均可。若无解,输出 `No solution.` 图的节点数不超过 $100$。
输入格式
第一行两个正整数 $n,m$ 表示点数和边数。 接下来 $m$ 行,每行三个正整数 $x,y,z$,表示节点 $x,y$ 之间有一条长度为 $z$ 的边。
输出格式
输出一个最小环的方案:按环上顺序输出最小环上的点。若最小环不唯一,输出任意一个均可。若无解,输出 `No solution.`
输入样例
复制
4 6 1 2 40 1 3 50 1 4 60 2 3 10 2 4 30 3 4 20
输出样例
复制
2 3 4
分类标签
图论