题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？
输入输出格式
输入格式：
输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行为N个用空格隔开的非负整数，表示Ki。
输出格式：
输出文件仅一行，即最少按键次数,若无法到达，则输出-1。
输入输出样例
输入样例#1：
5 1 5
3 3 1 2 5
输出样例#1：
3
Solution:
本题，入眼搜索。直接dfs就ok了。这里我选择的是spfs跑最短路求解，首先将某一层连有向边到它能到达的层数并将边权设置为1，然后从s到t跑一遍最短路就ok了。
代码：
#include<bits/stdc++.h>
#define il inline
using namespace std;
const int N=,inf=;
il int gi()
{
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=;
while(x>=''&&x<='')a=a*+x-,x=getchar();
return f?-a:a;
}
int n,a,b,k,dis[],h[N],cnt;
struct edge{
int to,net,w;
}e[N];
bool vis[N];
il void add(int u,int v,int w)
{
e[++cnt].to=v,e[cnt].net=h[u],e[cnt].w=w,h[u]=cnt;
}
il int spfa(int s,int t)
{
queue<int>q;
for(int i=;i<=;i++)dis[i]=inf;
q.push(s);dis[s]=;vis[s]=;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=;
for(int i=h[u];i;i=e[i].net)
{
int v=e[i].to;
if(dis[v]>dis[u]+){
dis[v]=dis[u]+;
if(!vis[v])q.push(v),vis[v]=;
}
}
}
return dis[t];
}
int main()
{
n=gi(),a=gi(),b=gi();
for(int i=;i<=n;i++){
k=gi();
if(k+i<=n)add(i,k+i,);
if(i-k>)add(i,i-k,);
}
int ans=spfa(a,b);
printf("%d",ans==inf?-:ans);
return ;
}