问题标题: 酷町堂：4189   无向图的最小环

题目描述 Description

给定一个无向图，求图中一个至少包含3个点的环，环上的结点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小环的方案。若无解，输出“No solution.”。图的结点数不超过100。

输入描述 Input Description

第一行两个正整数n, m, 表示结点数和边数。
接下来m行，每行三个正整数x, y, z，表示结点x, y之间有一条长度为z的边。

输出描述 Output Description

输出一个最小环的方案：按环上顺序输出最小环上的点。若最小环不唯一，输出任意一个均可。若无解，输出“No solution.”。

样例输入 Sample Input

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

样例输出 Sample Output

2 1 3 5

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=105;
const int inf=1<<10;
int n,m;
int a[M][M];
int f[M][M];
int ans=inf;
inline int get(){
    char c=getchar();
    int res=0;
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9'){
        res=(res<<3)+(res<<1)+c-'0';
        c=getchar();
    }
    return res;
}
int main(){
    n=get(),m=get();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            a[i][j]=inf,f[i][j]=inf;
    for (int i=1;i<=m;i++){         
    int x,y,z;         
    x=get();y=get();z=get();
        a[x][y]=a[y][x]=f[x][y]=f[y][x]=z;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                if (i==j||j==k||i==k) continue;
                ans=min(ans,a[k][j]+a[i][k]+f[i][j]);
                f[i][j]=min(f[i][j],f[i][k]+f[j][k]);
            }
        }     
    }
    if (ans==inf) cout<<"No solution."<<endl; 
    else cout<<ans<<endl;
    return 0;
}

10分代码，只能输出No solution.