#zDLlydlt60x6105. 观光之旅 Sightseeing Trip

观光之旅 Sightseeing Trip

好的,这是整理好的完整题目描述,包含样例解释,格式清晰,适合上传平台。


题目描述

给定一张无向图,求图中一个至少包含 33 个点的环,要求:

  • 环上节点不重复。
  • 环上边的长度之和最小。

这个问题称为无向图的最小环问题
你需要输出最小环的节点顺序(按环的顺序),如果最小环不唯一,输出任意一个均可。
如果图中不存在至少 33 个点的环,则输出 No solution.


输入格式

第一行两个整数 NNMM,表示图的点数和边数。
接下来 MM 行,每行三个整数 u,v,lu, v, l,表示点 uu 和点 vv 之间有一条无向边,长度为 ll

输出格式

输出一行,包含最小环的所有节点(按环顺序输出),用空格分隔。
如果不存在这样的环,输出 No solution.

数据范围

  • 1N1001 \le N \le 100
  • 1M100001 \le M \le 10000
  • 1l<5001 \le l < 500

输入样例

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

输出样例

1 3 5 2

样例解释

图的构造

点数 N=5N=5,边数 M=7M=7,边如下(为了方便,重复边取最小长度,因为是无向图):

  1. 1-4: 1
  2. 1-3: 300(但下面有一条更小的 1-3 边,见第 3 条)
  3. 1-3: 10(长度 10 替换上面的 300)
  4. 1-2: 16
  5. 2-3: 100
  6. 2-5: 15
  7. 5-3: 20

注意:输入中 1-3 有两条不同长度边(300 和 10),应取较短的那条(10)作为实际距离,因为这是无向图的最小环问题,边权取实际最小权。


寻找最小环

环至少 3 个点。
考虑几个候选环:

  1. 环 1-2-3:边长 16 + 100 + 10 = 126
  2. 环 1-3-5-2:边长 10 + 20 + 15 + 16 = 61
    • 1→3: 10
    • 3→5: 20
    • 5→2: 15
    • 2→1: 16
  3. 环 2-3-5:边长 100 + 20 + 15 = 135
  4. 环 1-4-?:1-4 只有一条边 1,4 只连 1,无法构成环(至少 3 个点)。

显然 环 1-3-5-2 长度 61 是当前最小的。

是否有更小的?
检查环 1-2-5-3:
1→2: 16
2→5: 15
5→3: 20
3→1: 10
总和 16+15+20+10 = 61,与上面相同(只是顺序不同)。
所以 61 是最小值。


输出方案

输出可以是 1 3 5 2(按环顺序)。
也接受 1 2 5 3 等,只要是一个长度为 61 的环即可。


最终输出1 3 5 2