Description：

$n(n\le 10^5)$ 个点构成的有向图，有 $m(m\le10^5)$ 条连通信息，信息有三种：

$1$ $u$ $v$ $w$ ，表示存在一条边权为 $w$ 的有向边 $(u,v)$ ；

$2$ $u$ $L$ $R$ $w$ ，表示 $\forall v\in[L,R]$ ，存在一条边权为 $w$ 的有向边 $(u,v)$ ；

$3$ $u$ $L$ $R$ $w$ ，表示 $\forall v\in[L,R]$ ，存在一条边权为 $w$ 的有向边 $(v,u)$ 。

其中 $w\le10^9$ 。求点 $s$ 到每个点的最短路，不存在输出 $−1$ 。

Solution：

线段树优化建图，由于是有向图，建立两棵线段树，第一棵线段树父亲向孩子连边权为 $0$ 的边，第二棵线段树孩子向父亲连边权为 $0$ 的边，两棵线段树的叶子节点连边权为 $0$ 的双向边。对于信息 $1$ ，从第一棵树的叶子连向第二棵树的叶子，信息 $2$ 从第二棵树的叶子连向第一棵树对应区间。信息 $3$ 从第二棵树的区间连向第一棵树的叶子。 $SPFA$ 求最短路即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m,s;

#define MAXN 100010

struct edge

{

	int to,nxt,v;

}e[30 * MAXN * 2];

int edgenum = 0;

int lin[MAXN << 2] = {0};

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

{

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

	return;

}

int to[MAXN][2];

struct node

{

	int lc,rc;

}t[MAXN << 2];

int ptr = 0;

int newnode(){return ++ptr;}

int root[2];

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

void build(int &rt,int l,int r,int k)

{

	rt = newnode();

	if(l == r)

	{

		to[l][k] = rt;

		return;

	}

	build(t[rt].lc,l,mid,k);

	build(t[rt].rc,mid + 1,r,k);

	if(k == 0)

	{

		add(rt,t[rt].lc,0);

		add(rt,t[rt].rc,0);

	}

	else

	{

		add(t[rt].lc,rt,0);

		add(t[rt].rc,rt,0);

	}

	return;

}

void add2(int rt,int p,int L,int R,int k,int l,int r)

{

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

	{

		add(p,rt,k);

		return;

	}

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

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

	return;

}

void add3(int rt,int L,int R,int p,int k,int l,int r)

{

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

	{

		add(rt,p,k);

		return;

	}

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

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

	return;

}

typedef long long ll;

ll d[MAXN << 2];

bool v[MAXN << 2];

bool vis[MAXN << 2];

int main()

{

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

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

	int x,a,b,w,l,r;

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

	{

		add(to[i][0],to[i][1],0);

		add(to[i][1],to[i][0],0);

	}

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

	{

		scanf("%d",&x);

		if(x == 1)

		{

			scanf("%d%d%d",&a,&b,&w);

			add(to[a][0],to[b][1],w);

		}

		if(x == 2)

		{

			scanf("%d%d%d%d",&a,&l,&r,&w);

			add2(root[0],to[a][1],l,r,w,1,n);

		}

		if(x == 3)

		{

			scanf("%d%d%d%d",&a,&l,&r,&w);

			add3(root[1],l,r,to[a][0],w,1,n);

		}

	}

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

	memset(v,false,sizeof(v));

	memset(vis,false,sizeof(vis));

	queue<int> q;

	q.push(to[s][0]);

	d[to[s][0]] = 0;v[to[s][0]] = true;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		vis[k] = true;

		v[k] = false;

		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;

				if(!v[e[i].to])

				{

					v[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

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

	{

		if(!vis[to[i][0]])printf("-1 ");

		else printf("%I64d ",d[to[i][0]]);

	}

	puts("");

	return 0;

}