rt，写的是 $O(n\log^2n)$ 的树剖加线段树，但一直 RE 最后两个点。数组一开大就 MLE，一开小就 RE，现在怀疑不是数组的问题。

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int N=2500000,P=50100,M=5000000;
#define inf 0x3f3f3f3f

int to[M],nxt[M],head[N],w[M],type[M];
int dfn[P],rnk[P],dep[P],siz[P],son[P],fa[P],top[P];
int idx=1,n,m,in1,in2,in3,in4,in5,op,s;
int query_num,dfs_cnt,id;
int dis[N],vis[N],idt[P][2];

int fat[P];
int find(int x){return fat[x]==x?x:fat[x]=find(fat[x]);}

int build_new_point(){
    id++;return id;
}

void add(int u,int v,int c,int f){
    idx++;to[idx]=v;nxt[idx]=head[u];
    head[u]=idx;w[idx]=c;type[idx]=f;
}

struct Query{
    int u1,v1,u2,v2,w;
}query[N];

struct Node{
    int x,dis;
}now;

bool operator < (Node a,Node b){
    return a.dis>b.dis;
}

priority_queue <Node> q;

void Dijskra(){
    memset(dis,0x3f,sizeof dis);
    q.push(Node{s,0});dis[s]=0;
    while(!q.empty()){
        now=q.top();q.pop();
        if(vis[now.x]) continue;
        vis[now.x]=1;
        for(int i=head[now.x];i;i=nxt[i]){
            int v=to[i];
            if(dis[v]<dis[now.x]+w[i]) continue;
            dis[v]=dis[now.x]+w[i];
            q.push(Node{v,dis[v]});
        }
    }
}

void dfs_1(int s,int gr){
    fa[s]=gr;dep[s]=dep[gr]+1;
    siz[s]=1;son[s]=-1;
    for(int i=head[s];i;i=nxt[i]){
        int v=to[i];
        if(v==gr) continue;
        if(!type[i]) continue;
        dfs_1(v,s);
        siz[s]+=siz[v];
        if(son[s]==-1||siz[son[s]]<siz[v]) son[s]=v;
    }
}

void dfs_2(int s,int tp){
    top[s]=tp;
    dfn[s]=++dfs_cnt;
    rnk[dfs_cnt]=s;
    if(son[s]==-1) return ;
    add(son[s]+n,s+n,0,0);
    add(s+2*n,son[s]+2*n,0,0);
    dfs_2(son[s],tp);
    for(int i=head[s];i;i=nxt[i]){
        int v=to[i];
        if(!type[i]) continue;
        if(v==son[s]||v==fa[s]) continue;
        dfs_2(v,v);
    }
}

struct STn{
    int l,r;
};
struct ST{
    STn a[P<<2];
    void build(int p,int l,int r){
        a[p].l=l;a[p].r=r;
        if(a[p].l==a[p].r){
            idt[p][0]=build_new_point();
            idt[p][1]=build_new_point();
            add(idt[p][0],rnk[a[p].l],0,0);
            add(rnk[a[p].l],idt[p][1],0,0);
            return ;
        }
        int mid=(a[p].l+a[p].r)>>1;
        build(p<<1,l,mid);build(p<<1|1,mid+1,r);
        idt[p][0]=build_new_point();
        idt[p][1]=build_new_point();
        add(idt[p][0],idt[p<<1][0],0,0);
        add(idt[p][0],idt[p<<1|1][0],0,0);
        add(idt[p<<1][1],idt[p][1],0,0);
        add(idt[p<<1|1][1],idt[p][1],0,0);
    }
    void connect(int p,int point,int l,int r,int f){
        if(l>r||a[p].r<l||a[p].l>r) return ;
        if(l<=a[p].l&&a[p].r<=r){
            if(f) add(point,idt[p][0],0,0);
            else add(idt[p][1],point,0,0);
            return ;
        }
        int mid=(a[p].l+a[p].r)>>1;
        if(l<=mid) connect(p<<1,point,l,r,f);
        if(r>mid) connect(p<<1|1,point,l,r,f);
    }
}tree;

void add_edge_one_to_two(int point,int x,int y,int f){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        if(f) add(point,x+n,0,0);
        else add(x+2*n,point,0,0);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]) swap(x,y);
    tree.connect(1,point,dfn[y],dfn[x],f);
}

void add_edge_two_to_two(int query_id){
    int u1=query[query_id].u1,v1=query[query_id].v1;
    int u2=query[query_id].u2,v2=query[query_id].v2;
    int w=query[query_id].w;
    int uu=build_new_point();
    int vv=build_new_point();
    add(uu,vv,w,0);
    add_edge_one_to_two(vv,u2,v2,1);
    add_edge_one_to_two(uu,u1,v1,0);
    /*
    建立一个入点和一个出点
    由入点向出点连边权为w的边
    由出点向u2-v2上的重链顶分别连边权为0的边
    由出点向u2-v2的剩余部分的线段树对应部分连边
    由u1-v1的重链顶向入点连边权为0的边
    由u1-v1的剩余部分的线段树向入点连边
    f=1 由点向区间，f=0 由区间向点
    */
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    id=3*n;
    /*
    对于每一个点另外建立一个入点和一个出点
    入点连向该点连向出点
    入点在重链上从下往上连边
    出点在重链上从上往下连边
    */
    for(int i=1;i<=n;i++) fat[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d%d%d",&in1,&in2,&in3,&in4,&in5);
            if(find(in1)!=find(in2)||find(in3)!=find(in4)) continue;
            query[++query_num]=Query{in1,in2,in3,in4,in5};
        }
        if(op==2){
            scanf("%d%d%d",&in1,&in2,&in3);
            if(find(in1)==find(in2)) continue;
            add(in1,in2,in3,1);add(in2,in1,in3,1);
            fat[find(in1)]=find(in2);
        }
    }
    for(int i=1;i<=n;i++)
        add(i+n,i,0,0),add(i,i+2*n,0,0);
    for(int i=1;i<=n;i++)
        if(!dfn[i]){
            dfs_1(i,0);
            dfs_2(i,i);
        }
    tree.build(1,1,n);
    for(int i=1;i<=query_num;i++)
        add_edge_two_to_two(i);
    Dijskra();
    for(int i=1;i<=n;i++) 
        if(dis[i]==inf) cout<<"-1 ";
        else cout<<dis[i]<<' ';
    cout<<'\n';
    return 0;
}