b_aw_观光之旅（floyd最小环路径）

给定一张无向图，求图中一个至少包含3个点的环，环上的节点不重复，并且环上的边的长度之和最小（输出任意一种路径）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105, inf=0x3f3f3f3f;
ll n,m,g[N][N],f[N][N],p[N][N];
vector<int> path;
void getPath(int i, int j) {
    int k=p[i][j];
    if (k==0) return;
    update_path(i,k);
    path.push_back(k);
    update_path(k,j);
}
ll floyd() {
    ll len=inf;
    for (int k=1; k<=n; k++) {
        for (int i=1; i<k-1; i++) 
        for (int j=i+1; j<k; j++) if (f[i][j]+g[i][k]+g[k][j]<len) {
            len=f[i][j]+g[i][k]+g[k][j];
            path.clear(), path.push_back(i);
            getPath(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 (f[i][k]+f[k][j]<f[i][j]) {
            f[i][j]=f[i][k]+f[k][j];
            p[i][j]=k;
        }
    }
    return len;
}
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1; i<=n; i++)
    for (int j=1; j<=n; j++) if (i!=j)
        f[i][j]=g[i][j]=inf;
    for (int i=0; i<m; i++) {
        ll u,v,w; cin>>u>>v>>w;
        g[u][v]=g[v][u]=min(g[u][v],w);
    }
    memcpy(f,g,sizeof g);
    ll len=floyd();
    if (len==inf) cout<<"No solution.";
    else for (int x : path) cout<<x<<' ';
    return 0;
}