算法

(Floyd) $O(n^3)$

设环的形式是：i<->k<->j , i<-->j （i,j,k不同） 
floyd是典型的插点算法，每次插入点k，为此，在点k被[插入前]可计算i-j-k这个环
即此时中间节点为：1~k-1，即我们已经算出了任意i<->j的最短道路，中间经过的节点可以为 (1,2,3,...,k-1)
我们只需枚举所有以k为环中最大节点的环即可。

pos[i][j]:i~j的最短路中经过的点是k(即由这个状态转移过来)，且这个k是此路径中编号最大的点(除i,j)//根据Floyd算法实质决定
这条道路存在以下两条性质
1.在i~j的最短道路中，一定没有环(显然)
2.设i,j之间的最短道路经过点k(不同于i,j)，则i~k , k~j之间必然没有交集

2证：
如果有交集,设交点为k'(k' < k,根据Floyd算法实质相关)，则存在道路：
i<->k'<->j , 由于[i<->k'] < [i<->k] , [j->k'] < [j->k] 
显然这条道路更小，和假设矛盾所以一定没有交集

对于pos[i][j]，如果pos[i][j] == 0 : 说明i~j的最短路没有经过其他节点

因此借用性质2来求解道路，注意书写顺序，确保最后输出顺序正确
每次把i <-> j 之间划分成 i<->k , k<->j

C++ 代码

#include <iostream>
#include <cstring>
#include <string>
#include <vector>

using namespace std ;

const int N = 110 , M = 10010 , INF = 0x3f3f3f3f ;


typedef long long LL ;
int g[N][N] , d[N][N] ;
int pos[N][N] ; //记录当前状态由哪个点转移过来
vector<int> path ;
int n , m ;

//确保顺序正确
void dfs(int i , int j )    //i->j之间的路，输出i到j之间不包括i和j的道路
{
    int k = pos[i][j] ;

    if( k == 0 )    return ;    //如果是0，说明i,j之间不经过除i，j之外的其他点

    dfs(i , k); //i->newk
    path.push_back(k);  //k
    dfs(k , j); //newk->j

}

void get_path(int i , int j , int k )
{
    path.clear() ;
    path.push_back(k);  //边界
    path.push_back(i);
    dfs(i , j) ;    //k->i->j->k
    path.push_back(j);
}

int main()
{
    cin >> n >> m ; 

    memset(g , 0x3f ,sizeof g) ;
    for(int i = 0 ; i <= n ; i++ )  g[i][i] = 0 ;

    int a , b , c ;
    for(int i = 0 ; i < m ; i++ )
    {
        cin >> a >> b >> c ;
        g[a][b] = g[b][a] = min(g[a][b] , c) ;
    }

    memcpy(d , g , sizeof d );  //原图
    long long res = INF ;

    for(int k = 1 ; k <= n ; k++ )
    {
        //至少包含三个点的环所经过的点的最大编号是k
        for(int i = 1 ; i < k ; i++ )  //至少包含三个点，i，j，k不重合
            for(int j = i + 1 ; j < k ; j ++ )
            if(res > (LL)g[i][j] + d[i][k] + d[k][j] )
            {
                res = g[i][j] + d[i][k] + d[k][j] ;
                get_path(i , j , k) ;
            }

        for(int i = 1 ; i <= n ; i++ )
            for(int j = 1 ; j <= n ; j++ )
                if(g[i][j] > g[i][k] + g[k][j])
                {
                    g[i][j] = g[i][k] + g[k][j] ;
                    pos[i][j] = k ; 
                }
    }

    if(res == INF)  
        cout << "No solution." << endl;
    else
    {
        for(auto x : path)
            cout << x << ' ' ;
        cout << endl;
    }

    return 0;
}