【题目描述】：

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

【输入描述】：

第一行两个正整数 n,m表示点数和边数。

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

【输出描述】：

输出一个最小环的边权之和。若无解，输出 “No solution.”

【样例输入】： 5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20

【样例输出】： 61

【时间限制、数据范围及描述】：

时间：1s 空间：512M

对于 20%的数据：1<=n<=10；

对于100%的数据：1<=n<=100；边权<=300。

对着floyd的模板打了半天，感觉for循环好多···

不过这道题模板改改就能用。

（不要纠结数组为什么是dijsktra的缩写）

 

 

#include
     
      #include
      
       #include
       
        #include
        
         #define mem(a,b) memset(a,b,sizeof(a))using namespace std;const int MAX=105;const int oo=100000000;int n,m;int dist[MAX][MAX],a[MAX][MAX];int s[MAX][MAX];int ans[MAX];int hh;inline int mn(int x,int y){
   return x
         
          y?x:y;}void init(){    int i,j;    int u,v,w;    for (i=1;i<=n;i++){        for (j=1;j<=n;j++){            dist[i][j]=a[i][j]=(i==j?0:oo);        }    }    mem(s,0);    ans[0]=0;    for (i=1;i<=m;i++){        scanf("%d%d%d",&u,&v,&w);        a[u][v]=mn(a[u][v],w);        dist[u][v]=dist[v][u]=a[v][u]=a[u][v];    }}void dfs(int u,int v){    int k=s[u][v];    if (k==0){        ans[++ans[0]]=v;        return;    }    dfs(u,k);    dfs(k,v);}void floyd(){    int i,j,k;    hh=oo;    for (k=1;k<=n;k++){        for (i=1;i
          
           dist[i][k]+dist[k][j]){ s[i][j]=k; dist[i][j]=dist[i][k]+dist[k][j]; } } } }}int main(){ freopen ("trip.in","r",stdin); freopen ("trip.out","w",stdout); init(); int i,j; while (~scanf("%d%d",&n,&m)){ init(); floyd(); if (hh==oo){ puts("No solution."); } else{ for (i=1;i