线段树优化建图做法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;
}