无向图最小环问题

把当前 $i$ 和 $j$ 间的最短路存到 $d[i][j]$ 里
用当前枚举到的中间节点充当 $k$
这时当前的 $d[i][j]$ 代表的最短路上不可能出现大于等于k的数
此时枚举 $i$ 和 $j$ 均小于 $k,i,j$ 没有顺序，更新最小环是d数组存的是上一轮的d值

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
typedef long long LL;
int n,m,x,y,z,ans = 1e9,a[N][N],pos[N][N];
LL d[N][N];
vector <int> path;
// pos[i][j]:i到j的最短路要经过pos[i][j]这个中转点
void get_path(int x,int y)
{
    int k = pos[x][y];
    if(!k) return;
    get_path(x,k);
    path.push_back(k);
    get_path(k,y);
}
int main()
{
    memset(a,0x3f,sizeof a);
    memset(d,0x3f,sizeof d);
    cin>>n>>m;
    for(int i = 1;i<=n;i++) d[i][i] = 0;
    while(m--)
    {
        cin>>x>>y>>z;
        d[x][y] = d[y][x] = min(d[x][y],(LL) z);
        a[x][y] = a[y][x] = d[x][y];
    }
    for(int k = 1;k<=n;k++)
    {
        for(int i = 1;i<k;i++)
            for(int j = i+1;j<k;j++)
                if(d[i][j]+a[j][k]+a[k][i] < ans)
                {
                    ans = d[i][j]+a[j][k]+a[k][i];
                    path.clear();
                    path.push_back(i);
                    get_path(i,j);
                    path.push_back(j);
                    path.push_back(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(ans == 1e9)
    {
        cout << "No solution." << '\n';
        return 0;
    }
    for(int x:path) cout << x << ' ';
    return 0;
}