空间跳跃(Space Jump) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, s, t;
    if (!(cin >> n >> s >> t)) return 0;
    vector<long long> l(n + 1), r(n + 1), h(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> l[i] >> r[i] >> h[i];
    }
    if (s == t) {
        cout << 0 << "\n";
        return 0;
    }
    int V = 2 * n + 2;
    int goal = 2 * n + 1;
    vector<vector<pair<int, long long>>> adj(V);
    for (int i = 1; i <= n; ++i) {
        int uL = 2 * i - 1, uR = 2 * i;
        adj[uL].push_back({uR, r[i] - l[i]});
        adj[uR].push_back({uL, r[i] - l[i]});
        auto addDrop = [&](int uNode, long long x) {
            int bestJ = -1;
            long long bestH = -1;
            for (int j = 1; j <= n; ++j) {
                if (h[j] < h[i] && l[j] <= x && x <= r[j]) {
                    if (h[j] > bestH) {
                        bestH = h[j];
                        bestJ = j;
                    }
                }
            }
            if (bestJ != -1) {
                long long drop = h[i] - h[bestJ];
                if (bestJ == t) {
                    adj[uNode].push_back({goal, drop});
                } else {
                    int vL = 2 * bestJ - 1, vR = 2 * bestJ;
                    adj[uNode].push_back({vL, drop + (x - l[bestJ])});
                    adj[uNode].push_back({vR, drop + (r[bestJ] - x)});
                }
            }
        };
        addDrop(uL, l[i]);
        addDrop(uR, r[i]);
    }
    const long long INF = (1LL << 58);
    vector<long long> dist(V, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    int startNode = 2 * s - 1;
    dist[startNode] = 0;
    pq.push({0, startNode});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;
        if (u == goal) break;
        for (auto& edge : adj[u]) {
            int v = edge.first;
            long long nd = d + edge.second;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push({nd, v});
            }
        }
    }
    if (dist[goal] >= INF) cout << -1 << "\n";
    else cout << dist[goal] << "\n";
    return 0;
}