Description：

$n$ 个点， $m$ 组边，每条边形如从 $(a,b)$ 到 $(c,d)$ 中每个点建无向边，求从第 $p$ 个点到所有点的最短路。

$1\leqslant n\leqslant 5\times10^5,1\leqslant m\leqslant 10^5$

Solution：

线段树优化最短路见图还是很显然的，像 CF787D Legacy 那样建两棵线段树，一棵内向一棵外向，然后外向向内向连边，但是 $(a,b)$ 和 $(c,d)$ 会各有 $\log n$ 条边，直接建的边数是 $m\log^2n$ 级别的，于是对于每组边新建一个点，然后外向向新点连边，新点向外向连边，最后求出来的最短路除以二就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,p;

#define MAXN 5000100

struct edge

{

	int to,nxt,v;

}e[MAXN * 5];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int v)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = v;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int pos[MAXN];

struct node

{

	int lc,rc;

}t[MAXN];

int ptr = 0;

int newnode(){return ++ptr;}

int root[2];

#define mid ((l + r) >> 1)

void build(int &rt0,int &rt1,int l,int r)

{

	if(l == r)

	{

		pos[l] = rt0 = rt1 = newnode();

		return;

	}

	rt0 = newnode();rt1 = newnode();

	build(t[rt0].lc,t[rt1].lc,l,mid);

	build(t[rt0].rc,t[rt1].rc,mid + 1,r);

	add(rt0,t[rt0].lc,0);add(t[rt1].lc,rt1,0);

	add(rt0,t[rt0].rc,0);add(t[rt1].rc,rt1,0);

	return;

}

void get(int type,int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{

		if(type == 1)add(rt,k,1);

		else add(k,rt,1);

		return;

	}

	if(L <= mid)get(type,t[rt].lc,L,R,k,l,mid);

	if(R > mid)get(type,t[rt].rc,L,R,k,mid + 1,r);

	return;

}

int d[MAXN];

bool v[MAXN];

int main()

{

	scanf("%d%d%d",&n,&m,&p);

	build(root[0],root[1],1,n);

	int l1,r1,l2,r2;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);

		int k;

		k = newnode();get(1,root[1],l1,r1,k,1,n);get(0,root[0],l2,r2,k,1,n);

		k = newnode();get(1,root[1],l2,r2,k,1,n);get(0,root[0],l1,r1,k,1,n);

	}

	priority_queue< pair<int,int> > q;

	q.push(make_pair(0,pos[p]));

	memset(d,0x3f,sizeof(d));

	d[pos[p]] = 0;

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(v[k])continue;

		v[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	for(int i = 1;i <= n;++i)printf("%d\n",d[pos[i]] >> 1);

	return 0;

}