BZOJ3073: [Pa2011]Journeys(线段树优化建图 Dijkstra)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define Pair pair<int, int> 
#define MP(x, y) make_pair(x, y)
using namespace std;
const int MAXN = 300010, MAXM = 2500010;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, P, tot;
struct Edge {
    int u, v, w, nxt;
}E[MAXM << 3];
int head[MAXM], num = 0;
inline void AddEdge(int x, int y, int z) {E[num] = (Edge) {x, y, z, head[x]}; head[x] = num++;}
struct Node {
    int ls, rs, l, r;
}T[MAXM];
int ra, rb, pos[MAXM], vis[MAXM], dis[MAXM];
void Build(int &k, int ll, int rr, int opt) {
    k = ++tot;
    T[k].l = ll; T[k].r = rr; 
    if(ll == rr) {if(opt == 1) pos[ll] = k; return ;}
    int mid = (ll + rr) >> 1;
    Build(T[k].ls, ll, mid, opt); Build(T[k].rs, mid + 1, rr, opt);
    if(opt == 1) AddEdge(T[k].ls, k, 0), AddEdge(T[k].rs, k, 0);
    else AddEdge(k, T[k].ls, 0), AddEdge(k, T[k].rs, 0);
}
void AddLeaf(int k) {
    if(T[k].l == T[k].r) {AddEdge(k, pos[T[k].l], 0); return ;}
    AddLeaf(T[k].ls); AddLeaf(T[k].rs);
}
void TreeAdd(int k, int ll, int rr, int to, int opt) {
    if(ll <= T[k].l && T[k].r <= rr) {opt == 1 ? AddEdge(k, to, 0) : AddEdge(to, k, 0); return ;}
    int mid = (T[k].l + T[k].r) >> 1;
    if(ll <= mid) TreeAdd(T[k].ls, ll, rr, to, opt); 
    if(rr >  mid) TreeAdd(T[k].rs, ll, rr, to, opt);
}
 
void Dijstra() {
    memset(dis, 0x7f, sizeof(dis)); dis[pos[P]] = 0; 
    priority_queue<Pair> q; 
    q.push(MP(0, pos[P]));
    while(!q.empty()) {
        int p = q.top().second; q.pop();
        if(vis[p]) continue; vis[p] = 1;
        for(int i = head[p]; ~i; i = E[i].nxt) {
            int to = E[i].v;
            if(!vis[to] && (dis[to] > dis[p] + E[i].w)) 
                dis[to] = dis[p] + E[i].w, q.push(MP(-dis[to], to));
        }
    }
}
void Add(int a, int b, int c, int d) {
    int p1 = ++tot, p2 = ++tot;
    TreeAdd(ra, a, b, p1, 1); 
    AddEdge(p1, p2, 1);
    TreeAdd(rb, c, d, p2, 0);   
}
int main() {    
    memset(head, -1, sizeof(head));
    N = read(); M = read(); P = read();
    Build(ra, 1, N, 1); Build(rb, 1, N, 0); AddLeaf(rb);
    for(int i = 1; i <= M; i++) {
        int a = read(), b = read(), c = read(), d = read();
        Add(a, b, c, d); Add(c, d, a, b);
    }
    Dijstra();
    for(int i = 1; i <= N; i++) printf("%d\n", dis[pos[i]]);
    return 0;
}
/*
 
*/