Legacy（线段树优化建边跑Dijkstra）

Legacy

线段树优化建边，开两颗线段树：
对于线段树1，自顶向下连边。对于线段树2，自底向上连边。
然后对于op1我们直接连边即可。
对于op2（u -> [l, r] cost = w），这个操作在线段树1上完成即可。
对于op3（[l, r] -> v cost = w），这个操作在线段树2上完成即可。
最后跑一遍Dijkstra最短路即可。

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;

typedef long long ll;

const int N = 2e6 + 10;

int n, m, s, tree1[N], tree2[N], tot;

int head[N], to[N], nex[N], value[N], vis[N], cnt = 1;

ll dis[N];

void add(int x, int y, int w) {
    to[cnt] = y;
    nex[cnt] = head[x];
    value[cnt] = w;
    head[x] = cnt++;
}

int build1(int rt, int l, int r) {
    if(l == r) {
        return tree1[rt] = l;
    }
    tree1[rt] = ++tot;
    int lid = build1(lson);
    int rid = build1(rson);
    add(tree1[rt], lid, 0);
    add(tree1[rt], rid, 0);
    return tree1[rt];
}

int build2(int rt, int l, int r) {
    if(l == r) {
        return tree2[rt] = l;
    }
    tree2[rt] = ++tot;
    int lid = build2(lson);
    int rid = build2(rson);
    add(lid, tree2[rt], 0);
    add(rid, tree2[rt], 0);
    return tree2[rt];
}

void add1(int rt, int l, int r, int u, int L, int R, int w) {
    if(l >= L && r <= R) {
        add(u, tree1[rt], w);
        return ;
    }
    if(L <= mid) add1(lson, u, L, R, w);
    if(R > mid)  add1(rson, u, L, R, w);
}

void add2(int rt, int l, int r, int v, int L, int R, int w) {
    if(l >= L && r <= R) {
        add(tree2[rt], v, w);
        return ;
    }
    if(L <= mid) add2(lson, v, L, R, w);
    if(R > mid)  add2(rson, v, L, R, w);
}

typedef pair<ll, int> pli;

priority_queue<pli, vector<pli>, greater<pli> > q;

void Dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    q.push(make_pair(0, s));
    while(q.size()) {
        int temp = q.top().second;
        q.pop();
        if(vis[temp]) continue;
        vis[temp] = 1;
        for(int i = head[temp]; i; i = nex[i]) {
            if(dis[to[i]] > dis[temp] + value[i]) {
                dis[to[i]] = dis[temp] + value[i];
                q.push(make_pair(dis[to[i]], to[i]));
            }   
        }
    }
    for(int i = 1; i <= n; i++) {
        printf("%lld%c", dis[i] == 0x3f3f3f3f3f3f3f3f ? -1 : dis[i], i == n ? '\n' : ' ');
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d %d %d", &n, &m, &s);
    tot = n;
    build1(1, 1, n);
    build2(1, 1, n);
    for(int i = 1; i <= m; i++) {
        int op, x, y, l, r, w;
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d %d %d", &x, &y, &w);
            add(x, y, w);
        }
        else if(op == 2) {
            scanf("%d %d %d %d", &x, &l, &r, &w);//x -> [l, r] cost w.
            add1(1, 1, n, x, l, r, w);
        }
        else {
            scanf("%d %d %d %d", &x, &l, &r, &w);//[l, r] -> x cost w.
            add2(1, 1, n, x, l, r, w);
        }
    }
    Dijkstra();
    return 0;
}