最小环
cpp
int n,m;
int adj[N][N],d[N][N],pos[N][N];
int path[N],cnt;
void get_path(int i,int j){
if(pos[i][j]==0)return;
get_path(i,pos[i][j]);
path[cnt++]=pos[i][j];
get_path(pos[i][j],j);
}
void solve(){
cin>>n>>m;
memset(adj,0x3f,sizeof adj);
for(int i=1;i<=n;i++)adj[i][i]=0;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
adj[u][v]=adj[v][u]=min(adj[u][v],w);
}
memcpy(d,adj,sizeof d);
LL ans=INF;
for(int k=1;k<=n+1;k++){
for(int i=1;i<k;i++){
for(int j=i+1;j<k;j++){
if((LL)d[i][j]+adj[i][k]+adj[k][j]<ans){
ans=(LL)d[i][j]+adj[i][k]+adj[k][j];
cnt=0;
path[cnt++]=k;
path[cnt++]=i;
get_path(i,j);
path[cnt++]=j;
}
}
}
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.\n";
else for(int i=0;i<cnt;i++)cout<<path[i]<<" \n"[i==cnt-1];
}