1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e2+5;
 4 int G[N][N];
 5 int main()
 6 {
 7     int n,m;
 8     scanf("%d%d",&n,&m);
 9     for(int i=1;i<=m;i++)
10     {
11         int u,v,w;
12         scanf("%d%d%d",&u,&v,&w);
13         G[u][v]=G[v][u]=w;
14     }
15     for(int k=1;k<=n;k++)
16     {
17         //如果存在一个最短环，那么必然有最大的序列，令其为k，根据更新顺序可知算法的正确性； 
18         for(int i=1;i<=k-1;i++)
19         for(int j=i+1;j<=k-1;j++)//必须要取到两个点才能与k构成环 
20         ans=max(ans,dis[i][j]+G[i][k]+G[k][j]);//此时的dis[i][j]是通过比k的k`更新的最短距离
21         
22         for(int i=1;i<=n;i++)
23         for(int j=1;j<=n;j++)
24         dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 
25     }
26     
27     return 0;
28 }