xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

int  N,M;
int  g[ 110 ][ 110 ];
int  d[ 110 ][ 110 ];
int  m[ 110 ][ 110 ];
int  c = 0 ,ans[ 110 ];
void  dfs( int  x, int  y){
    
if (m[x][y] ==- 1 return ;
    dfs(x,m[x][y]);
    ans[
++ c] = m[x][y];
    dfs(m[x][y],y);
}
int  main()
{
    
while ( 1 ){
        scanf(
" %d " , & N); 
        
if (N ==- 1 break ;
        scanf(
" %d " , & M);
        
for ( int  i = 1 ;i <= N; ++ i)
            
for ( int  j = 1 ;j <= N; ++ j)
                g[i][j]
= 0xFFFFFFF ;
        
int  x,y,z;
        
for ( int  i = 1 ;i <= M; ++ i){
            scanf(
" %d%d%d " , & x, & y, & z);
            
if (g[x][y] > z)
                g[x][y]
= g[y][x] = z;
        }
        
for ( int  i = 1 ;i <= N; ++ i)
            
for ( int  j = 1 ;j <= N; ++ j)
                d[i][j]
= g[i][j];
        memset(m,
- 1 , sizeof (m));
        
int  Min = 10000000 ;
        
for ( int  k = 1 ;k <= N; ++ k){
            
for ( int  i = 1 ;i < k; ++ i)
                
for ( int  j = i + 1 ;j < k; ++ j)
                    
if (d[i][k] + d[k][j] + g[i][j] < Min){
                        Min
= d[i][k] + d[k][j] + g[i][j];
                        c
= 2 ;
                        ans[
1 ] = k;
                        ans[c]
= i;
                        dfs(i,j);
                        ans[
++ c] = j;
                    }
            
for ( int  i = 1 ;i <= N; ++ i)
                
for ( int  j = i + 1 ;j <= N; ++ j)
                    
if (g[i][j] > g[i][k] + g[k][j]){
                        g[i][j]
= g[i][k] + g[k][j];
                        g[j][i]
= g[i][j];
                        m[i][j]
= m[j][i] = k;
                    }
        }
        
if (Min == 10000000 ) printf( " No solution.\n " );
        
else {
            
for ( int  i = 1 ;i < c; ++ i)
                printf(
" %d  " ,ans[i]);
            printf(
" %d\n " ,ans[c]);
        }
    }
    
return   0 ;
}




posted on 2009-05-29 16:35 xfstart07 阅读(196) 评论(0)  编辑 收藏 引用 所属分类: 代码库

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理