MX 58pts 求助 玄关

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;
#define lint long long int
#define ulint unsigned long long
#define sint short int

lint a[3500005],tou[3500005],qu[3500005],zhi[3500005],hou[3500005],tu[3500005],tes[3500005],cnt,n,m,s;
bool vis[3500005];
priority_queue<pair<lint,lint>> q;
const lint ns = 2e6;
lint xud = 1e6;

void add(lint u,lint v,lint w)
{
    cnt++;
    qu[cnt] = v;
    hou[cnt] = tou[u];
    zhi[cnt] = w;
    tou[u] = cnt;
    tes[cnt] = u;
}

void build(lint p,lint l,lint r)
{
    if(l == r)
    {
        a[l] = p;
        return ;
    }
    lint mid = (l + r) / 2;
    add(p,p * 2,0);
    add(p,p * 2 + 1,0);
    add(p * 2 + ns,p + ns,0);
    add(p * 2 + 1 + ns,p + ns,0);
    build(p * 2,l,mid);
    build(p * 2 + 1,mid + 1,r);
}

void chg(lint p,lint l,lint r,lint lx,lint rx,lint v,lint w,lint op)
{
    if(l >= lx && r <= rx)
    {
        if(op == 1)
        {
            add(p + ns,v,w);
        }
        else
        {
            add(v,p,w);
        }
        return ;
    }
    lint mid = (l + r) / 2;
    if(lx <= mid)
    {
        chg(p * 2,l,mid,lx,rx,v,w,op);
    }
    if(rx > mid)
    {
        chg(p * 2 + 1,mid + 1,r,lx,rx,v,w,op);
    }
}

void dij(lint s)
{
    memset(tu,127,sizeof(tu));
    tu[s] = 0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(vis[u] == 1)
        {
            continue;
        }
        vis[u] = 1;
        for(int i = tou[u];i != 0;i = hou[i])
        {
            int v = qu[i];
            if(tu[v] > tu[u] + zhi[i])
            {
                tu[v] = tu[u] + zhi[i];
                q.push(make_pair(-tu[v],v));
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> s;
    build(1,1,n);
    for(int i = 1;i <= n;i++)
    {
        add(a[i],a[i] + ns,0);
        add(a[i] + ns,a[i],0);
    }
    for(int i = 1;i <= m;i++)
    {
        lint l,r,ll,rr;
        cin >> l >> r >> ll >> rr;
        chg(1,1,n,l,r,xud,1,1);
        chg(1,1,n,ll,rr,xud,1,2);
        xud++;
        chg(1,1,n,l,r,xud,1,2);
        chg(1,1,n,ll,rr,xud,1,1);
        xud++;
    }
    dij(a[s]);
    for(int i = 1;i <= n;i++)
    {
        cout << tu[a[i]] / 2 << '\n';
    }
//  cout << '\n';
//  for(int i = 1;i <= n;i++)
//  {
//      if(tu[a[i] + ns] == 2147483647000)
//      {
//          cout << -1 << '\n';
//      }
//      else
//      {
//          cout << tu[a[i] + ns] / 2 << '\n';
//      }
//  }
//  for(int i = 1;i <= cnt;i++)
//  {
//      cout << tes[i] << ' ' << qu[i] << ' ' << zhi[i] << '\n';
//  }
    return 0;
}