求助 44pts

卡了一晚上都没过去：

#define debug
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double
#define fir first
#define sec second
#define lep( i, l, r ) for ( int i = ( l ); i <= ( r ); i ++ )
#define rep( i, r, l ) for ( int i = ( r ); i >= ( l ); i -- )
#define gep( i, x ) for ( int i = head[( x )]; i; i = edges[i].next)

char _c; bool _f; template < class T > inline void read ( T &x ) {
    _f = 0, x = 0;
    while ( _c = getchar (), !isdigit (_c) ){
        if ( _c == '-' ) { _f = 1; }
    }
    while ( isdigit (_c) ){
        x = x * 10 + _c - '0', _c = getchar ();
        if (_f) { x = -x; }
    }
}

const int N = 5e5 + 5;
const int M = N << 2;

int tree[M], tree2[M];

int n, m, p, cnt;

int head[M * 5], tot;

struct Node {
  int to, w, next;
} edges[M * 5];

void add ( int u, int v, int w ) {
  tot ++;
  edges[tot].to = v;
  edges[tot].w = w;
  edges[tot].next = head[u];
  head[u] = tot;
}

void build ( int node, int lt, int rt ) {
  cnt = max ( cnt, node );
  if ( lt == rt ) {
    add ( lt, node + n, 0 );
    return ;
  }
  int mid = lt + rt >> 1;
  int ls = node << 1, rs = node << 1 | 1;
  add ( ls + n, node + n, 0 ), add ( rs + n, node + n, 0 );
  build ( node << 1, lt, mid ), build ( node << 1 | 1, mid + 1, rt );
}

void build2 ( int node, int lt, int rt ) {
  if ( lt == rt ) {
    add ( node + n + cnt, lt, 0 );
    return ;
  }
  int mid = lt + rt >> 1;
  int ls = node << 1, rs = node << 1 | 1;
  add ( node + n + cnt, ls + n + cnt, 0 ), add ( node + n + cnt, rs + n + cnt, 0 );
  build2 ( node << 1, lt, mid ), build2 ( node << 1 | 1, mid + 1, rt );
}

void update ( int node, int lt, int rt, int x, int y, int k ) {
  if ( y < lt || x > rt ) {
    return ;
  }
  if ( x <= lt && rt <= y ) {
    add ( node + n, k, 0 );
    return ;
  }
  int mid = lt + rt >> 1;
  update ( node << 1, lt, mid, x, y, k ), update ( node << 1 | 1, mid + 1, rt, x, y, k );
}

void update2 ( int node, int lt, int rt, int x, int y, int k ) {
  if ( y < lt || x > rt ) {
    return ;
  }
  if ( x <= lt && rt <= y ) {
    add ( k, node + n + cnt, 1 );
    return ;
  }
  int mid = lt + rt >> 1;
  update2 ( node << 1, lt, mid, x, y, k ), update2 ( node << 1 | 1, mid + 1, rt, x, y, k );
}

int dis[N];
bool vis[N];

void bfs ( int s ) {
  deque < int > q;
  memset ( dis, 0x7f, sizeof ( dis ) );
  dis[s] = 0;
  q.push_back ( s );
  while ( !q.empty () ) {
    int x = q.front ();
    q.pop_front ();
    if ( vis[x] ) {
      continue;
    }
    vis[x] = true;
    for ( int i = head[x]; i; i = edges[i].next ) {
      if ( dis[x] + edges[i].w < dis[edges[i].to] ) {
        dis[edges[i].to] = dis[x] + edges[i].w;
        if ( !edges[i].w ) {
          q.push_front ( edges[i].to );
        }
        else {
          q.push_back ( edges[i].to );
        }
      }
    }
  }
}

void Solve () {
  cin >> n >> m >> p;
  build ( 1, 1, n );
  build2 ( 1, 1, n );
  for ( int i = 1; i <= cnt; i ++ ) {
    add ( i + n + cnt, i + n, 0 );
  }
  int r = 2 * cnt + n;
  for ( int i = 1; i <= m; i ++ ) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    update ( 1, 1, n, a, b, ++ r ), update2 ( 1, 1, n, c, d, r );
    update ( 1, 1, n, c, d, ++ r ), update2 ( 1, 1, n, a, b, r );
  }
  bfs ( p );
  for ( int i = 1; i <= n; i ++ ) {
    cout << dis[i] << '\n';
  }
}

signed main() {
#ifdef debug
  freopen ( "test.in", "r", stdin );
  freopen ( "test.out", "w", stdout );
#endif
  Solve ();
  return 0;
}