遗产传送门(Legacy) 题解

思路分析

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

参考代码

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

const long long INF = (1LL << 60);
int n, q, s;
int totNodes;
vector<vector<pair<int, long long>>> adj;
vector<int> outId, inId;

void build(int u, int l, int r) {
    outId[u] = ++totNodes;
    inId[u] = ++totNodes;
    if (l == r) {
        adj[outId[u]].push_back({l, 0});
        adj[l].push_back({inId[u], 0});
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    adj[outId[u]].push_back({outId[u << 1], 0});
    adj[outId[u]].push_back({outId[u << 1 | 1], 0});
    adj[inId[u << 1]].push_back({inId[u], 0});
    adj[inId[u << 1 | 1]].push_back({inId[u], 0});
}

void addOut(int u, int l, int r, int ql, int qr, int from, long long w) {
    if (ql <= l && r <= qr) {
        adj[from].push_back({outId[u], w});
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) addOut(u << 1, l, mid, ql, qr, from, w);
    if (qr > mid) addOut(u << 1 | 1, mid + 1, r, ql, qr, from, w);
}

void addIn(int u, int l, int r, int ql, int qr, int to, long long w) {
    if (ql <= l && r <= qr) {
        adj[inId[u]].push_back({to, w});
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) addIn(u << 1, l, mid, ql, qr, to, w);
    if (qr > mid) addIn(u << 1 | 1, mid + 1, r, ql, qr, to, w);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> q >> s)) return 0;
    totNodes = n;
    adj = vector<vector<pair<int, long long>>>(9 * n + 20);
    outId = vector<int>(4 * n + 10, 0);
    inId = vector<int>(4 * n + 10, 0);
    build(1, 1, n);
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int v, u;
            long long w;
            cin >> v >> u >> w;
            adj[v].push_back({u, w});
        } else if (t == 2) {
            int v, l, r;
            long long w;
            cin >> v >> l >> r >> w;
            addOut(1, 1, n, l, r, v, w);
        } else {
            int v, l, r;
            long long w;
            cin >> v >> l >> r >> w;
            addIn(1, 1, n, l, r, v, w);
        }
    }
    vector<long long> dist(totNodes + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        long long ans = (dist[i] == INF ? -1 : dist[i]);
        cout << ans << (i == n ? "\n" : " ");
    }
    return 0;
}