sunkehappy

         又是一道典型的最短路徑的題目，當(dāng)然也可以用搜索，我現(xiàn)在在學(xué)習(xí)最短路徑，所以就用Dijsktra來(lái)做的，一開(kāi)始時(shí)WA了好幾次，是因?yàn)檫@一題是應(yīng)該抽象出來(lái)一個(gè)有向圖，而我卻是用了無(wú)向圖，所以一直WA。最后改了一下，然后就過(guò)了。

#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 ;
}