洛谷P6175 无向图最小环问题（利用Floyd算法求解）

无向图最小环问题研究

题目描述

对于一个给定的无向图，需要找到一个包含至少三个顶点的环，该环中的节点互不重复，且环中所有边的权重总和达到最小值。这一问题被称作无向图中的最小环问题。在本题中，要求输出该最小环的边权总和，若不存在这样的环，则输出 No solution.。

输入格式

首行给出两个正整数 n,m，分别代表图中的顶点数目与边的数量。

随后的 m 行中，每一行包含三个正整数 u,v,d，用以描述顶点 u 与顶点 v 之间存在一条权值为 d 的连接边。

输出格式

计算具有最小边权和的环的边权总和。若无法找到符合条件的环，则输出 No solution.。

样例分析与呈现

样例输入 #1

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

样例输出结构解析

    61
    
    
      
    

提示

一种可实施的策略为：$1-3-5-2