随笔 - 19, 文章 - 0, 评论 - 2, 引用 - 0
数据加载中……

hdu1548 A strange lift

         又是一道典型的最短路径的题目,当然也可以用搜索,我现在在学习最短路径,所以就用Dijsktra来做的,一开始时WA了好几次,是因为这一题是应该抽象出来一个有向图,而我却是用了无向图,所以一直WA。最后改了一下,然后就过了。

#include <stdio.h>
#define DEBUG 1
const int N=300 ;
const int Max = 10000000 ;
int n, map[N][N], used[N], dis[N] ;

void Dijkstra( int a, int b )
{
    
int i, j, index, min ;
    
for( i=1; i<=n; ++i ){
        dis[i] 
= map[a][i] ;
        used[i] 
= 0 ;
    }

    used[a] 
= 1 ;
    
for( i=1; i<=n; ++i ){
        index 
= a ;
        min 
= Max ;
        
for( j=1; j<=n; ++j ){
               
if!used[j] && min > dis[j] ){
                   min 
= dis[j] ;
                   index 
= j ;
             }

        }

        used[index] 
= 1 ;
        
for( j=1; j<=n; ++j ){
            
if( dis[j] > dis[index]+map[index][j] )
                dis[j] 
= dis[index]+map[index][j] ;
        }

    }

    
if( dis[b] == Max ){
        
//printf("%d\n", dis[b] ) ;
        printf("-1\n") ;
    }
       
    
else
        printf(
"%d\n", dis[b] ) ;
}


int main( )
{
    
#if DEBUG
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
    
#endif
    
    
int i, j, a, b, temp ;
    
while( scanf("%d"&n) && n ){
        
for( i=1; i<=n; ++i ){
               
for( j=1; j<=n; ++j )
                   map[i][j] 
= Max ;
               map[i][i] 
= 0 ;    
        }

        scanf(
"%d%d"&a, &b ) ;
        
for( i=1; i<=n; ++i ){
            scanf(
"%d"&temp ) ;
            
if( i - temp > 0 )
                map[i][i
-temp] = 1 ;
            
if( i + temp <= n )
                 map[i][i
+temp] = 1 ;
        }

        Dijkstra( a, b ) ;
    }
         
    
return 0 ;
}

posted on 2009-05-03 21:16 祝你好运! 阅读(277) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理