hdu1599+floyd最小环

floyd最外层的k循环在循环到某个数ki时，前面以0到ki-1为中间结点的最短路径已经求出。

所有在内层的双循环之前再用一个双循环记录已找到的最小环的值即可。

要开两个数组存图，一个图就表示原图，不能改变值，另一个用来记录最短路。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int g[110][110],n,m,dis[110][110];
 6 const int mmax=1<<30;
 7 int main()
 8 {
 9     int i,j,k;
10     while(scanf("%d%d",&n,&m)!=EOF)
11     {
12         for(i=1;i<=n;i++)
13         {
14             for(j=1;j<=n;j++)
15             {
16                 if(i==j) g[i][j]=0;
17                 else g[i][j]=mmax;
18             }
19         }
20         for(i=1;i<=m;i++)
21         {
22             int a,b,c;
23             scanf("%d%d%d",&a,&b,&c);
24             if(c<g[a][b])
25             g[a][b]=g[b][a]=c;
26         }
27         for(i=1;i<=n;i++)
28             for(j=1;j<=n;j++)
29             dis[i][j]=g[i][j];
30         int mincircle=mmax;
31         for(k=1;k<=n;k++)
32         {
33             for(i=1;i<k;i++)
34             {
35                 for(j=1;j<k;j++)
36                 {
37                     if(g[i][k]<mmax&&g[k][j]<mmax&&dis[j][i]<mmax&&i!=j&&j!=k&&i!=k)
38                         mincircle=min(mincircle,g[i][k]+g[k][j]+dis[j][i]);
39                 }
40             }
41             for(i=1;i<=n;i++)
42             {
43                 for(j=1;j<=n;j++)
44                 {
45                     if(dis[i][k]<mmax&&dis[k][j]<mmax)
46                     dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
47                 }
48             }
49         }
50         if(mincircle<mmax) printf("%d
",mincircle);
51         else printf("It's impossible.
");
52     }
53     return 0;
54 }