本题是一个经典的优化建图问题，线段树优化建图、利用贪心性质分析之后 dp 都可以，这里只介绍一种基于非负最短路特性的隐式松弛做法。

对于非负最短路，想要构成其最短路径树有一个关键的性质：每一个节点至多被松弛 1 次。

因此我们可以使用 set 或者区间染色并查集等数据结构，保存集合内尚未松弛的点。而从队列当中拿出一个已经松弛过的点之后，遍历其邻接且未松弛的点，将他们的最短距离确定，并加入队列即可。一个点遍历完之后，在集合中删掉这些松弛点，这样可以保证每一个点都只被遍历了 1 次。

总复杂度 $O(n\log n)$，即便是 python3 也能轻松通过。

#include <stdio.h>
#include <string.h>
#include <set>
#include <queue>
#include <algorithm>
inline int rd()
{
    int k = 0, f = 1;
    char s = getchar();
    while (s < '0' || s > '9') f = (s == '-') ? 0 : f, s = getchar();
    while (s >= '0' && s <= '9') k = (k << 1) + (k << 3) + (s ^ '0'), s = getchar();
    return f ? k : -k;
}
inline void wr(int x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) wr(x / 10);
    putchar((x % 10) ^ '0');
}
const int N = 100010;
int n;
int a[N], b[N], f[N];
bool vis[N];
std::set<int> s;
std::queue<int> q;
int main()
{
    n = rd();
    for (int i = 1; i <= n; ++i) a[i] = i - rd(), s.insert(i);
    for (int i = 1; i <= n; ++i) b[i] = rd();
    memset(f, 0xff, (n + 1) << 2);

    q.push(1), f[1] = 0, s.erase(1), vis[1] = 1;
    while (q.size())
    {
        int u = q.front();
        q.pop();
        auto st = s.lower_bound(std::min(n, u + 1)), cur = st, ed = s.lower_bound(std::min(n + 1, u + b[u] + 1));
        while (cur != ed)
        {
            int v = a[*cur];
            if (!vis[v]) f[v] = f[u] + 1, vis[v] = 1, q.push(v);
            ++cur;
        }
        s.erase(st, ed);
    }
    wr(f[n]);
}

这题的核心思想是把“跳跃 + 后退”转化成图上的最短路问题。 从第 i 个格子能跳到区间 [i+1, i+k[i]] 内的任意 j，然后落到 j−a[j] 上。 于是可以看成从 i 有边连向 (j−a[j])。每次跳跃的代价都是 1，所以整题就是求从 1 到 n 的最短路径，我们要用到BFS。 直接建图会超时，所以要用区间单调优化。 随着 BFS 按层推进，每个格子能跳到的右端总是单调不减的。我们用一个变量 maxs 记录当前已经扫描到的最右位置，每次只扩展还没访问过的新部分 [maxs+1, R]，这样每个位置只会被处理一次，不会重复访问。 这个方法使压缩成线性扫描，整个 BFS 过程的时间复杂度降为 O(n)。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[N], k[N], dist[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> k[i];

    for(int i = 1; i <= n; i++) a[i] = i - a[i]; 
    fill(dist, dist + n + 1, INF);
    dist[1] = 0;

    queue<int> q;
    q.push(1);

    int maxs = 1;
    while(!q.empty()) {
        int u = q.front(); 
        q.pop();
        int r = min(n, u + k[u]);
        for(int j = max(maxs + 1, u + 1); j <= r; j++) {
            int v = a[j];
            if(v >= 1 && dist[v] == INF) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
        maxs = max(maxs, r);
    }

    if(dist[n] == INF) cout << -1 << "\n";
    else cout << dist[n] << "\n";
    return 0;
}