题意：给N个点和Q条选项，有三种类型的选项：1.从u到v花费w修建一条路；2.从u到下标区间为[L,R]的点花费w修建一条路; 3.从下标区间为[L,R]的点到u花费w修建一条路。

然后求起点s到其余点的最短路。

 

如果直接暴力建图，建图本身就会超时。对于区间上的操作，考虑用线段树解决。线段树上的结点本身就能代表一段区间的点，所以在建图时，用树上的结点充当中间结点。（有点网络流的思想？）

因为要建一张有向图，所以图的点到树上结点要连边，反之亦然；但是在一棵线段树上双向连边就不能对所有的点跑最短路了（因为图中的点可能会在树上找到权值为0的回路回到自己）。

所以再建一棵线段树去表示反向连边的关系。

对每个树上结点从N+1开始编号，将其与之维护的区间中的点连一条花费为0的边。每次更新就是用把给定区间[L,R]囊括的所有树上结点与给定的u连边。操作2和操作3分别对应两棵线段树的结点。

#include
     
      #define lson rt<<1#define rson rt<<1|1#define Lson l,m,lson#define Rson m+1,r,rsonusing namespace std;typedef long long LL;const int maxn = 4e5+5;const LL INF = (1LL)<<60;struct Edge{    int to,next;    LL w;}edges[maxn<<4];int head[maxn<<4],tot;int ID[maxn<<2],rID[maxn<<2];int id;void init(int N){    memset(head,-1,sizeof(head));    tot=0;    id = N;}void AddEdge(int u,int v,LL w){    edges[tot] = (Edge){v,head[u],w};    head[u] = tot++;}void build(int l,int r,int rt,bool flag){    if(!flag) ID[rt] = ++id;    else rID[rt] = ++id;    if(!flag) {
   for(int i=l;i<=r;++i) AddEdge(ID[rt],i,0);}    else {
   for(int i=l;i<=r;++i) AddEdge(i,rID[rt],0);}    if(l==r) return;    int m = (l+r)>>1;    build(Lson,flag);    build(Rson,flag);}void update(int L,int R,LL w,int u,int l,int r,int rt,bool flag){    if(L<=l && R>=r){        if(!flag)AddEdge(u,ID[rt],w);        else AddEdge(rID[rt],u,w);        return;    }    int m =(l+r)>>1;    if(L<=m) update(L,R,w,u,Lson,flag);    if(R>m) update(L,R,w,u,Rson,flag);}LL d[maxn<<4];bool used[maxn<<4];struct HeapNode{    LL d;    int u;    bool operator <(const HeapNode & rhs) const {
   return d > rhs.d;}};void dijkstra(int s){           memset(used,0,sizeof(used));        priority_queue
      
        Q;        for(int i=0;i<=id;++i)    d[i]=INF;        d[s]=0;        Q.push((HeapNode){
    0,s});        while(!Q.empty()){            HeapNode x =Q.top();Q.pop();            int u =x.u;            if(used[u])  continue;            used[u]= true;            for(int i=head[u];~i;i=edges[i].next){                Edge & e = edges[i];                if(d[e.to] > d[u] + e.w){                    d[e.to] = d[u] +e.w;                    Q.push((HeapNode){d[e.to],e.to});                }            }        }    }int main(){    #ifndef ONLINE_JUDGE        freopen("in.txt","r",stdin);        freopen("out.txt","w",stdout);    #endif    int T,N,M,q,s,u,v,op,L,R;    LL w;    while(scanf("%d%d%d",&N,&q,&s)==3){        init(N);        build(1,N,1,0);        build(1,N,1,1);        while(q--){            scanf("%d",&op);            if(op==1){                scanf("%d%d%lld",&u,&v,&w);                AddEdge(u,v,w);            }            else if(op==2){                scanf("%d%d%d%lld",&u,&L,&R,&w);                update(L,R,w,u,1,N,1,0);            }            else{                scanf("%d%d%d%lld",&u,&L,&R,&w);                update(L,R,w,u,1,N,1,1);            }        }        dijkstra(s);        for(int i=1;i<=N;++i)            printf("%lld%c",d[i]==INF?-1:d[i],i==N?'\n':' ');    }    return 0;}