题解 | 空间跃迁

// 不会前缀和，看到题目即想到最短路，可以把空间折跃认为是跑到下一层，分层图dij即可

// 时间复杂度O(nlogn)

void solve() {
        ll n, k; rd(n, k);
        vector<vector<pll>> g(2 * n + 2);
        rep(i, 1, n - 1) {
            int x; rd(x);
            g[i].eb(i+1, x);
            g[n+i].eb(n+i+1, x);
        }
        rep(i, 1, n) {
            g[i].eb(max(n+1, n+i-k), 0ll);
            g[i].eb(min(2*n, n+i+k), 0ll);
        }
        priority_queue<pll, vector<pll>, greater<pll>> pq;
        vector<ll> dis(2*n + 2, INF);
        dis[1] = 0;
        pq.emplace(0, 1);
        while (!pq.empty()) {
            auto [wu, u] = pq.top(); pq.pop();
            for (auto& [v, w] : g[u]) {
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    pq.emplace(dis[v], v);
                }
            } 
        }
        println(min(dis[n], dis[2*n]));
    }