HDU1599 最小环

floyd新应用！！！！
View Code
 1 #include<stdio.h>
 2 const int maxn = 101;
 3 const int inf = 9999999;
 4 int n,m;
 5 int dis[ maxn ][ maxn ],mat[ maxn ][ maxn ];
 6 
 7 void floyd(){
 8     int ans=inf;
 9     for( int i=1;i<=n;i++ )
10         for( int j=1;j<=n;j++ )
11             dis[ i ][ j ]=mat[ i ][ j ];
12     for( int k=1;k<=n;k++ ){
13 
14         for( int i=1;i<k;i++ ){
15             for( int j=1;j<i;j++ ){
16                 if( ans>( dis[i][j]+mat[i][k]+mat[k][j] ) )
17                     ans=dis[i][j]+mat[i][k]+mat[k][j];
18             }
19         }
20 
21         for( int i=1;i<=n;i++ ){
22             for( int j=1;j<=n;j++ ){
23                 if( dis[i][k]!=inf && dis[k][j]!=inf && dis[i][j]>(dis[i][k]+dis[k][j]) )
24                     dis[i][j]=(dis[i][k]+dis[k][j]);
25             }
26         }
27 
28     }
29 
30      if(ans==inf)
31          printf("It's impossible.\n");
32      else 
33          printf("%d\n",ans); 
34 }
35 
36 int main(){
37     while( scanf("%d%d",&n,&m)==2 ){
38         for( int i=1;i<=n;i++ )
39             for( int j=1;j<=n;j++ )
40                 mat[ i ][j ]=inf;
41         int a,b,c;
42         while( m-- ){
43             scanf("%d%d%d",&a,&b,&c);
44             if( c<mat[ a ][ b ] )
45                 mat[ a ][ b ]=mat[ b ][ a ]=c;
46         }
47         floyd();
48     }
49     return 0;
50 }
keep moving...