SPFA
#include<stdio.h> #include<string.h> #include<math.h> #include<vector> #include<algorithm> using namespace std; const int maxn = 222; int k[maxn], ji[maxn]; vector<int> abc[maxn]; struct aaa{int node, tot;}dt[maxn*maxn]; bool cmp(const aaa&a, const aaa&b){return a.tot < b.tot;} int main() { int N, A, B, i, j; while (~scanf("%d", &N)) { if (N == 0) break; scanf("%d%d", &A, &B); for (i = 0; i < maxn; i++) ji[i] = 999999999, abc[i].clear(); for (i = 1; i <= N; i++) scanf("%d", &k[i]); for (i = 1; i <= N; i++) { if (i + k[i] <= N) abc[i].push_back(i + k[i]); if (i - k[i] >= 1)abc[i].push_back(i - k[i]); } ji[A] = 0;dt[0].node = A;dt[0].tot = 0;int b = 0; for (i = 0; i <= b; i++) { for (j = 0; j < abc[dt[i].node].size(); j++) { if (dt[i].tot + 1 < ji[abc[dt[i].node][j]]) { b++; dt[b].node = abc[dt[i].node][j]; dt[b].tot = dt[i].tot + 1; ji[abc[dt[i].node][j]] = dt[i].tot + 1; } } } if (ji[B] != 999999999)printf("%d ", ji[B]); else printf("-1 "); } return 0; }