飞机票
题意：
思路：
超级经典的一道题，有多种解法
BFS
开个标记数组，用队列，然后就判断找下去，找到就跳出，就能保证用的次数最少，没找到则是-1。
#include<bits/stdc++.h> using namespace std; queue<pair<int ,int >>mo; const int maxn=20005; int a[maxn]; int ans[maxn]; int sf[maxn]; int n; bool jg(int d){ if(d>=1&&d<=n){ return true; } return false; } int main() { memset(ans,-1,sizeof(ans)); int i,j,m,f; cin>>n>>m>>f; rep(i,1,n){ cin>>a[i]; } mo.push(make_pair(m,a[m])); sf[m]=1; if(m==f){ cout<<0<<endl; return 0; } while(!mo.empty()){ int x1=mo.front().first; int yy=mo.front().second; int ss=mo.front().first+yy; int xx=mo.front().first-yy; mo.pop(); if(jg(ss)&&sf[ss]==0){ sf[ss]=1; ans[ss]=ans[x1]+1; mo.push(make_pair(ss,a[ss])); if(ss==f) break; } if(jg(xx)&&sf[xx]==0){ sf[xx]=1; ans[xx]=ans[x1]+1; mo.push(make_pair(xx,a[xx])); if(ss==f) break; } } if(ans[f]!=-1) cout<<ans[f]+1<<endl; else cout<<-1<<endl; }
