题目描述：

题解：

最短路+线段树优化建图。

考虑本题的边是点->点、段->点和点->段，我们可以建线段树然后拆成入点和出点。

入点：儿子->父亲，边权为0；

出点：父亲->儿子，边权为0；

叶子：出点->入点，边权为0；

那么连续的一段可以用不超过$log\;n$个节点表示，最后跑最短路即可。

代码：

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;const int N = 100050;const ll  Inf = 0x3f3f3f3f3f3f3f3fll;template
          
           inline void read(T&x){    T f = 1,c = 0;char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}    x = f*c;}int n,Q,S,hed[N*10],cnt,tot;ll dis[N*10];bool vis[N*10];struct EG{    int to,nxt;    ll w;}e[30*N];void ae(int f,int t,ll w){    e[++cnt].to = t;    e[cnt].nxt = hed[f];    e[cnt].w = w;    hed[f] = cnt;}int sta[N],tl;struct segtree{    int s[N<<2][2];    void build(int l,int r,int u)    {        s[u][0]=++tot,s[u][1]=++tot;        if(l==r){ae(s[u][1],s[u][0],0);return ;}        int mid = (l+r)>>1;        build(l,mid,u<<1),build(mid+1,r,u<<1|1);        ae(s[u<<1][0],s[u][0],0),ae(s[u<<1|1][0],s[u][0],0);        ae(s[u][1],s[u<<1][1],0),ae(s[u][1],s[u<<1|1][1],0);    }    int query(int l,int r,int u,int qx,int k)    {        if(l==r)return s[u][k];        int mid = (l+r)>>1;        if(qx<=mid)return query(l,mid,u<<1,qx,k);        else return query(mid+1,r,u<<1|1,qx,k);    }    void query(int l,int r,int u,int ql,int qr,int k)    {        if(l==ql&&r==qr){sta[++tl]=s[u][k];return ;}        int mid = (l+r)>>1;        if(qr<=mid)query(l,mid,u<<1,ql,qr,k);        else if(ql>mid)query(mid+1,r,u<<1|1,ql,qr,k);        else query(l,mid,u<<1,ql,mid,k),query(mid+1,r,u<<1|1,mid+1,qr,k);    }    void print(int l,int r,int u)    {        if(l==r){
    if(dis[s[u][0]]==Inf)printf("-1 ");else printf("%lld ",dis[s[u][0]]);return ;}        int mid = (l+r)>>1;        print(l,mid,u<<1);print(mid+1,r,u<<1|1);    }}tr;struct Pair{    int x;ll y;    Pair(){}    Pair(int x,ll y):x(x),y(y){}    bool operator < (const Pair&a)const{
    return y>a.y;}};priority_queue
           
            q;void dij(){ memset(dis,0x3f,sizeof(dis)); S = tr.query(1,n,1,S,0); dis[S]=0;q.push(Pair(S,0)); while(!q.empty()) { Pair tp = q.top();q.pop(); int u = tp.x;if(vis[u])continue;vis[u] = 1; for(int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; if(dis[to]>dis[u]+e[j].w) { dis[to] = dis[u]+e[j].w; q.push(Pair(to,dis[to])); } } }}int main(){// freopen("tt.in","r",stdin); read(n),read(Q),read(S); tr.build(1,n,1); for(int op,a,b,c,d,i=1;i<=Q;i++) { read(op),read(a),read(b),read(c); if(op==1) { a = tr.query(1,n,1,a,0),b = tr.query(1,n,1,b,1); ae(a,b,c); }else { read(d); if(op==2) { int f = tr.query(1,n,1,a,0); tl = 0;tr.query(1,n,1,b,c,1); for(int j=1;j<=tl;j++) ae(f,sta[j],d); }else { tl = 0;tr.query(1,n,1,b,c,0); int t = tr.query(1,n,1,a,1); for(int j=1;j<=tl;j++) ae(sta[j],t,d); } } } dij(); tr.print(1,n,1); puts(""); return 0;}