用floyd找最小环

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=300+10;
int a[maxn][maxn],d[maxn][maxn],pos[maxn][maxn];//d[i][j]表示点i到j的最短距离，pos[i][j]表示点i到j路径的中转点，如果没有为0 
int n,m,ans=INF;
vector<int> path;//记录路径 
void get_path(int x,int y)//寻找路径 
{
    if(pos[x][y]==0)
    {
        return ;
    }
    get_path(x,pos[x][y]);//继续搜索x到x,y的中转点的中转点 
    path.push_back(pos[x][y]);
    get_path(pos[x][y],y);
}
int main()
{
    cin>>n>>m;
    memset(a,INF,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        a[i][i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        a[y][x]=a[x][y]=min(a[x][y],z);
    }
    memcpy(d,a,sizeof(a));//memcpy为复制，即把a数组复制到d数组 
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)
        {
            for(int j=i+1;j<k;j++)
            {
                if((long long)d[i][j]+a[j][k]+a[k][i]<ans)//一定要long long
                {
                    ans=d[i][j]+a[j][k]+a[k][i]; 
                    path.clear();//找到更小的环，清空路径 
                    path.push_back(i);//从i点开始走 
                    get_path(i,j);//遍历点i到j的路径 
                    path.push_back(j);//到达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==INF)
    {
        cout<<"No solution."<<endl;
    }
    else
    {
        for(int i=0;i<path.size();i++)
        {
            cout<<path[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

题目地址：https://ac.nowcoder.com/acm/contest/1055/F