莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 核心：基于dp思想，每次取以 k 为当前环中的最大编号的最小环，再比较各个最大编号为 k 的最小环
2. 当 d[i][j] 可以被 d[i][k] + d[k][j] 更新时，记录下当前的转移点 k
3. 一个最大编号为 k 的环的长度：d[i][j] + g[j][k] + g[k][i] (d[i][j]是最大编号为 k-1 的最小距离)

#include<bits/stdc++.h>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n,m;
int d[N][N],g[N][N];
int path[N],cnt;
int pos[N][N];

//顺序获得[i,j]中转移的点
void get_path(int i,int j)
{
    if(!pos[i][j]) return;
    int k=pos[i][j];
    get_path(i,k);
    path[cnt++]=k;
    get_path(k,j);
}

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

    memset(g,0x3f,sizeof g);

    //自己到自己是0
    for(int i=1;i<=n;i++) g[i][i]=0;

    //无向边建图
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=c;
    }

    memcpy(d,g,sizeof d);

    int res=INF;
    for(int k=1;k<=n;k++)
    {
        //一个环中 k 是最大编号
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++)
                if((long long)d[i][j]+g[j][k]+g[k][i]<res)
                {
                    res=d[i][j]+g[j][k]+g[k][i];
                    cnt=0;
                    path[cnt++]=j;
                    path[cnt++]=k;
                    path[cnt++]=i;
                    get_path(i,j);
                }

        // k 为最大编号更新所有最短距离
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(d[i][j]>d[i][k]+d[k][j])
                {
                    d[i][j]=d[i][k]+d[k][j];
                    pos[i][j]=k;
                }
    }

    if(res==INF) cout<<"No solution."<<endl;
    else for(int i=0;i<cnt;i++) cout<<path[i]<<' ';

    return 0;
}