学步园

这题乍一看是个搜索，但是仔细一想用最短路来做更简单啊，图论就是有意思，把每层楼可能到每层楼的路径保存为一个图

     1     2     3    4      5

1 M   M     M    1     M

2 M   M     M    M   M 

3 M   1       M    1    M 

4 M     1     M    M   M 

5 M   M   M     M   M   

1表示可以到达存在路径，M表示不可达

然后在图中求最短路，一次AC，so easy ,注意范围。。93ms，还很快

//////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 10000000;

int N,A,B;
int G[201][201];
int dist[201];
int Ki[201];

void Dijkstra(int v0)
{
     int vis[201];
     int min;
     int k;
     for(int i = 1; i <= N; i++)
     {
           vis[i] = 0;
           dist[i] = G[v0][i];
     }
     dist[v0] = 0;
     vis[v0] = 1;
     for(int v = 1; v <= N; v++)
     {
             min = MAX;
             for(int w = 1; w <= N; w++)
             {
                    if(!vis[w] && (dist[w] < min))
                    {
                          min = dist[w];
                          k = w;               
                    }
             }
             
             vis[k] = 1;
             for(int w = 1; w <= N; w++)
             {
                     if(!vis[w] && (min + G[k][w] < dist[w]))
                     {
                           dist[w] = min + G[k][w];
                     }
             }
     }
}

int main()
{
    while(cin>>N,N!=0)
    {
          cin>>A>>B;
          for(int i = 1; i <= N; i++)
          {
                 for(int j = 1; j <= N; j++)
                 {
                         G[i][j] = MAX;
                 }
          }
          for(int i = 1; i <= N; i++)
          {
                 cin>>Ki[i];
                 if(i + Ki[i] <= N)
                 {
                      G[i][i+Ki[i]] = 1;
                 }
                 if(i - Ki[i] >= 1)
                 {
                      G[i][i-Ki[i]] = 1;
                 }
          }
          Dijkstra(A);
          if(dist[B] < MAX)
                cout<<dist[B]<<endl;
          else
                cout<<"-1"<<endl;
    }
    return 0;
}