文件详细信息

下载本文件

本文件的大小为 1896 字节。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
typedef long long ll;
const int maxn=100005,maxm=300005;
int n,m,s,cnt,rt1,rt2;
int total,head[maxm],left[maxm],right[maxm],to[maxn*20],next[maxn*20],len[maxn*20];
int read(){
	int ch=getchar(),num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}
void add(int u,int v,int w){
	to[++total]=v;
	next[total]=head[u];
	head[u]=total;
	len[total]=w;
}
void build1(int&u,int l,int r){
	if(l==r){
		u=l;
		return;
	}
	u=++cnt;
	int m=(l+r)>>1;
	build1(left[u],l,m);
	build1(right[u],m+1,r);
	add(u,left[u],0);
	add(u,right[u],0);
}
void build2(int&u,int l,int r){
	if(l==r){
		u=l;
		return;
	}
	u=++cnt;
	int m=(l+r)>>1;
	build2(left[u],l,m);
	build2(right[u],m+1,r);
	add(left[u],u,0);
	add(right[u],u,0);
}
int ql,qr;
void update(int x,int l,int r,int u,int w,int type){
	if(ql<=l&&r<=qr){
		type==2?add(u,x,w):add(x,u,w);
		return;
	}
	int m=(l+r)>>1;
	if(ql<=m)update(left[x],l,m,u,w,type);
	if(qr>m)update(right[x],m+1,r,u,w,type);
}
const ll inf=0x3f3f3f3f3f3f3f3f;
bool inq[maxm];
ll dis[maxm];
std::priority_queue<std::pair<long long,int> >q;
void dijkstra(int s){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push(std::make_pair(0,s));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(inq[u])continue;
		inq[u]=true;
		for(int i=head[u];i;i=next[i]){
			int v=to[i],w=len[i];
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(std::make_pair(-dis[v],v));
			}
		}
	}
}
int main(){
	n=read(),m=read(),s=read();
	cnt=n;
	build1(rt1,1,n);
	build2(rt2,1,n);
	int op,u,v,w;
	while(m--){
		op=read();
		if(op==1){
			u=read(),v=read(),w=read();
			add(u,v,w);
		}else{
			u=read(),ql=read(),qr=read(),w=read();
			update(op==2?rt1:rt2,1,n,u,w,op);
		}
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)printf("%lld ",dis[i]<inf?dis[i]:-1ll);
	return 0;
}