RT

#include<bits/stdc++.h>
#include<queue>
using namespace std;
typedef long long ll;
const ll MAXN=4e5+5;
ll n,q,s,op,x,y,z,_l,_r;
struct edge{
	ll u,v,w,nxt;
}e[MAXN<<2];
ll head[MAXN<<2],edge_num;
void add_edge(ll From,ll To,ll Len){
	edge_num++;
	e[edge_num].u=From;
	e[edge_num].v=To;
	e[edge_num].w=Len;
	e[edge_num].nxt=head[From];
	head[From]=edge_num;
	return;
}
ll pos[MAXN];
struct node{
	ll id,now_dis;
	bool operator < (const node &oth)const{
		return now_dis<oth.now_dis;
	}
}t;
ll l[MAXN<<2],r[MAXN<<2],lson[MAXN<<2],rson[MAXN<<2],cnt,rt_in,rt_out;
ll dis[MAXN<<2];
bool vis[MAXN<<2];
void build_in(ll &id,ll L,ll R){
	id=++cnt;
	l[id]=L,r[id]=R;
	if(L==R){
		pos[L]=id;
		return;
	}
	ll mid=(L+R)>>1;
	build_in(lson[id],L,mid);
	build_in(rson[id],mid+1,R);
	add_edge(id,lson[id],0);
	add_edge(id,rson[id],0);
	return;
}
void build_out(ll &id,ll L,ll R){
	if(L==R){
		id=pos[L];
		return;
	}
	id=++cnt;
	l[id]=L,r[id]=R;
	ll mid=(L+R)>>1;
	build_out(lson[id],L,mid);
	build_out(rson[id],mid+1,R);
	add_edge(lson[id],id,0);
	add_edge(rson[id],id,0);
	return;
}
void add_in(ll id,ll L,ll R,ll UL,ll UR,ll pos,ll delta){
	if(L>R||UR<L||R<UL)return;
	if(UL<=L&&R<=UR){
		add_edge(pos,id,delta);
		return;
	}
	ll mid=(L+R)>>1;
	if(UL<=mid)add_in(lson[id],L,mid,UL,UR,pos,delta);
	if(UR>mid)add_in(rson[id],mid+1,R,UL,UR,pos,delta);
	return;
}
void add_out(ll id,ll L,ll R,ll UL,ll UR,ll pos,ll delta){
	if(L>R||UR<L||R<UL)return;
	if(UL<=L&&R<=UR){
		add_edge(id,pos,delta);
		return;
	}
	ll mid=(L+R)>>1;
	if(UL<=mid)add_out(lson[id],L,mid,UL,UR,pos,delta);
	if(UR>mid)add_out(rson[id],mid+1,R,UL,UR,pos,delta);
	return;
}
void dijkstra(ll st){
	priority_queue<node> pq;
	for(int i=1;i<=(n<<2);i++)dis[i]=1e18;
	dis[st]=0;
	pq.push((node){st,0});
	while(pq.size()){
		t=pq.top();
		pq.pop();
		if(vis[t.id])continue;
		for(int i=head[t.id];i;i=e[i].nxt){
			if(vis[e[i].v])continue;
			if(dis[e[i].v]>dis[t.id]+e[i].w){
				dis[e[i].v]=dis[t.id]+e[i].w;
				pq.push((node){e[i].v,dis[e[i].v]});
//					vis[e[i].v]=1;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>s;
	build_in(rt_in,1,n);
	build_out(rt_out,1,n);
	for(int i=1;i<=q;i++){
		cin>>op;
		if(op==1){
			cin>>x>>y>>z;
			add_edge(pos[x],pos[y],z);
		}
		else if(op==2){
			cin>>x>>_l>>_r>>z;
			add_in(rt_in,1,n,_l,_r,pos[x],z);
		}
		else{
			cin>>x>>_l>>_r>>z;
			add_out(rt_out,1,n,_l,_r,pos[x],z);
		}
	}
	dijkstra(pos[s]);
	for(int i=1;i<=n;i++){
		if(dis[pos[i]]!=1e18)cout<<dis[pos[i]]<<" ";
		else cout<<-1<<" ";
	}
	return 0;
}

不知道哪里挂了/ll