线段树优化建图做法68分TLE最后1点求助

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int hsh=2e6;
int n,m,s,vis[4500001],x1[500001],x2[500001],cnta;
int cnt,head[8000001];
struct edgee
{
	int to,nxt,w;
}e[8000001];
void edge(int u,int v,int w)
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	e[cnt].w=w;
	head[u]=cnt;
}
void build1(int i,int l,int r)
{
	vis[i]=1e9;
	if(l==r) 
	{
		x1[l]=i;
		edge(i,i+hsh,0);
		return ;
	}
	int mid=(l+r)>>1;
	build1(i<<1,l,mid);
	build1(i<<1|1,mid+1,r);
	edge(i,i<<1,0);
	edge(i,i<<1|1,0);
}
void build2(int i,int l,int r)
{
	vis[i+hsh]=1e9;
	if(l==r)
	{
		x2[l]=i+hsh;
		edge(i+hsh,i,0);
		return ;
	}
	int mid=(l+r)>>1;
	build2(i<<1,l,mid);
	build2(i<<1|1,mid+1,r);
	edge((i<<1)+hsh,i+hsh,0);
	edge((i<<1|1)+hsh,i+hsh,0);
}
void q1(int xi,int ww,int i,int l,int r,int lm,int rm)
{
	if(rm<l||lm>r) return ;
	if(lm<=l&&rm>=r)
	{
//		cout<<xi<<" "<<i<<" "<<ww<<endl;
		edge(xi,i,ww);
	}else
	{
		int mid=(l+r)>>1;
		q1(xi,ww,i<<1,l,mid,lm,rm);
		q1(xi,ww,i<<1|1,mid+1,r,lm,rm);
	}
}
void q2(int xi,int ww,int i,int l,int r,int lm,int rm)
{
//	cout<<"i:"<<i<<" "<<l<<" "<<r<<" "<<lm<<" "<<rm<<endl;
	if(rm<l||lm>r) return ;
//	cout<<":"<<i<<" "<<l<<" "<<r<<" "<<lm<<" "<<rm<<endl;
	if(lm<=l&&rm>=r)
	{
//		cout<<i+hsh<<" "<<xi<<" "<<ww<<endl;
		edge(i+hsh,xi,ww);
	}else
	{
		int mid=(l+r)>>1;
		q2(xi,ww,i<<1,l,mid,lm,rm);
		q2(xi,ww,i<<1|1,mid+1,r,lm,rm);
	}
}
queue<int> q;
void bfs()
{
	while(!q.empty()) q.pop();
	vis[x1[s]]=0;
	q.push(x1[s]);
	while(!q.empty())
	{
		int tp=q.front();
		q.pop();
		for(int i=head[tp];i;i=e[i].nxt)
		{
//			cout<<tp<<" "<<e[i].to<<" "<<e[i].w<<" "<<vis[tp]<<" "<<vis[e[i].to]<<endl;
			if(vis[e[i].to]>vis[tp]+e[i].w)
			{
//				cout<<"dtxj"<<endl;
				vis[e[i].to]=vis[tp]+e[i].w;
				q.push(e[i].to);
			}
		}
	}
}
signed main()
{
	scanf("%d%d%d",&n,&m,&s);
	build1(1,1,n);
	build2(1,1,n);
	cnta=2*hsh;
	for(int i=1;i<=m;i++)
	{
		int aa,bb,cc,dd;
		scanf("%d%d%d%d",&aa,&bb,&cc,&dd);
		cnta++;
		vis[cnta]=1e9;
		q2(cnta,0,1,1,n,aa,bb);
		q1(cnta,1,1,1,n,cc,dd);
		cnta++;
		vis[cnta]=1e9;
		q2(cnta,0,1,1,n,cc,dd);
		q1(cnta,1,1,1,n,aa,bb);
	}
	bfs();
//	for(int i=1;i<=n;i++) cout<<x1[i]<<"  "<<x2[i]<<endl;
	for(int i=1;i<=n;i++)
	{
		printf("%d\n",min(vis[x1[i]],vis[x2[i]]));
	}
	return 0;
}