又是一道典型的最短路徑的題目，當(dāng)然也可以用搜索，我現(xiàn)在在學(xué)習(xí)最短路徑，所以就用Dijsktra來做的，一開始時(shí)WA了好幾次，是因?yàn)檫@一題是應(yīng)該抽象出來一個(gè)有向圖，而我卻是用了無向圖，所以一直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 ;
}