无向图最小环
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
int n, m, uu, vv, ww, a[105][105], b[105][105], pos[105][105], ans;
const int oo=0x3f3f3f3f;
vector<int> vec;
void dig(int x, int y){
if(pos[x][y]==0) return ;
dig(x, pos[x][y]);
vec.push_back(pos[x][y]);
dig(pos[x][y], y);
}
int main(){
cin>>n>>m;
memset(a, 0x3f, sizeof(a));
memset(b, 0x3f, sizeof(b));
for(int i=1; i<=n; i++)
a[i][i] = b[i][i] = 0;
for(int i=1; i<=m; i++){
scanf("%d %d %d", &uu, &vv, &ww);
a[uu][vv] = a[vv][uu] = b[uu][vv] = b[vv][uu] = min(a[uu][vv], ww);
}
ans = oo;
for(int k=1; k<=n; k++){
for(int i=1; i<k; i++)
for(int j=i+1; j<k; j++){
if((ll)b[i][j]+a[j][k]+a[k][i]<ans){
ans = b[i][j] + a[j][k] + a[k][i];
vec.clear();
vec.push_back(i);
dig(i, j);
vec.push_back(j);
vec.push_back(k);
}
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(b[i][j]>b[i][k]+b[k][j]){
b[i][j] = b[i][k] + b[k][j];
pos[i][j] = k;
}
}
if(ans==oo) printf("No solution.
");
else{
for(int i=0; i<vec.size(); i++)
printf("%d ", vec[i]);
printf("
");
}
return 0;
}