文件详细信息

下载本文件

本文件的大小为 3233 字节。

#include<cstdio>
#include<cstring>
#include<queue>
namespace IO{
	const int ARR_SIZE=1<<24;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	void getstr(char*str){
		char ch=gc();
		while(ch=='\r'||ch=='\n'||ch==' '||ch=='\t')ch=gc();
		while(ch!='\r'&&ch!='\n'&&ch!=' '&&ch!='\t'&&ch!=EOF)*(str++)=ch,ch=gc();
		*str='\0';
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt;
		if(a==0)pc('0');
		cnt=0;
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
	void putstr(const char*str){
		while(*str!='\0')pc(*(str++));
	}
}
using IO::read;
using IO::getstr;
using IO::write;
using IO::putstr;
const int maxn=500005,maxm=100005,maxlogn=20;
const int maxnode=(maxn<<3)+maxm+(maxn<<1),maxedge=(maxn<<3)+maxn+2*maxlogn*maxm*2;
int n,m,p;
int head[maxnode],total,node_cnt;
struct Edge{
	int to,next,len;
}e[maxedge];
void add(int u,int v,int w){
	e[++total]=Edge{v,head[u],w};
	head[u]=total;
}
struct Tree{
	int tree_id;
	struct Seg{
		int l,r,id;
	}t[maxn<<2];
	int id[maxn];
	void build(int u,int l,int r){
		if(u==1)t[u].id=++node_cnt;
		if(l==r){
			id[l]=u;
			return;
		}
		t[u].l=++node_cnt;
		t[t[u].l].id=node_cnt;
		t[u].r=++node_cnt;
		t[t[u].r].id=node_cnt;
		if(tree_id==1){
			add(t[u].l,t[u].id,0);
			add(t[u].r,t[u].id,0);
		}else{
			add(t[u].id,t[u].l,0);
			add(t[u].id,t[u].r,0);
		}
		int m=(l+r)>>1;
		build(t[u].l,l,m);
		build(t[u].r,m+1,r);
	}
	void modify(int u,int l,int r,int ql,int qr,int new_node){
		if(ql<=l&&r<=qr){
			if(tree_id==1)add(t[u].id,new_node,1);
			else add(new_node,t[u].id,0);
			return;
		}
		int m=(l+r)>>1;
		if(m>=ql)modify(t[u].l,l,m,ql,qr,new_node);
		if(m<qr)modify(t[u].r,m+1,r,ql,qr,new_node);
	}
}t1,t2;
struct Data{
	int dis,u;
};
bool operator<(const Data a,const Data b){
	return a.dis>b.dis;
}
int dis[maxnode];
bool vis[maxnode];
std::priority_queue<Data>q;
void dijkstra(int s){
	memset(dis,31,sizeof(dis));
	q.push(Data{dis[s]=0,s});
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u])continue;
		vis[u]=true;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].len){
				dis[v]=dis[u]+e[i].len;
				q.push(Data{dis[v],v});
			}
		}
	}
}
int main(){
	read(n),read(m),read(p);
	t1.tree_id=1,t2.tree_id=2;
	t1.build(1,1,n);
	t2.build(1,1,n);
	for(int i=1;i<=n;i++)add(t2.id[i],t1.id[i],0);
	int a,b,c,d;
	for(int i=1;i<=m;i++){
		read(a),read(b),read(c),read(d);
		node_cnt++;
		t1.modify(1,1,n,a,b,node_cnt);
		t2.modify(1,1,n,c,d,node_cnt);
		node_cnt++;
		t1.modify(1,1,n,c,d,node_cnt);
		t2.modify(1,1,n,a,b,node_cnt);
	}
	dijkstra(t1.id[p]);
	for(int i=1;i<=n;i++)write(dis[t1.id[i]]),pc('\n');
	return 0;
}