题目链接神仙题，马上把本蒻苟搞死的那种。我一开始想的是dijkstra套线段树。一个点代表一个区间，用区间查询来得出该点的dist值。结果完美的过了2个test（两个样例），然后wa在第3个test上。想到是因为区间与单点之间的转移问题，然后就没有然后了。看题解真的给大佬跪了orz。打死我也想不到啊。我们先建一个长度n的线段树。然后建立两组节点in[i],out[i]，线段树上的每一个节点分配一个in编号，一个out编号。一个（in）建边指向自己的两个孩子，一个（out）指向自己的祖先。权值均为0，然后，在此基础上再改咋建图，咋建图。最后跑一边dijkstra。下面是ac代码：
//Iamjustapingfanren//notagod,thanks.#include<iostream>#include<queue>#include<vector>#include<cstdio>#include<cstring>#include<string>#include<map>#include<algorithm>#include<cstdlib>#definelllonglongusingnamespacestd;constintN=1e6+5;constllinf=1e16;inthe[N],ver[N<<1],ne[N<<1];boolvis[N];lle[N<<1];lldis[N];intin[N<<1],out[N<<1];inttot,n,m,s;priority_queue<pair<ll,int>>q;structNode{intl,r;}tr[N<<2];voidadd(intx,inty,llw){ver[++tot]=y;ne[tot]=he[x];e[tot]=w;he[x]=tot;}intcnt=1;voidbuild(intp,intl,intr){tr[p].l=l;tr[p].r=r;if(l==r){in[p]=out[p]=l;return;}intmid=(l+r)>>1;in[p]=++cnt;out[p]=++cnt;build(p<<1,l,mid);build(p<<1|1,mid+1,r);add(in[p],in[p<<1],0);add(in[p],in[p<<1|1],0);add(out[p<<1],out[p],0);add(out[p<<1|1],out[p],0);}voidbuildeg(intp,intk,intl,intr,llw,boolflag){if(l<=tr[p].l&&tr[p].r<=r){if(flag)add(out[p],k,w);elseadd(k,in[p],w);return;}intmid=(tr[p].l+tr[p].r)>>1;if(l<=mid)buildeg(p<<1,k,l,r,w,flag);if(r>mid)buildeg(p<<1|1,k,l,r,w,flag);}voiddij(){for(inti=0;i<=cnt;i++)dis[i]=inf;dis[s]=0;q.push(make_pair(0,s));while(q.size()){intx=q.top().second;q.pop();if(vis[x])continue;vis[x]=1;for(inti=he[x];i;i=ne[i]){inty=ver[i];if(dis[y]>dis[x]+e[i]){dis[y]=dis[x]+e[i];q.push(make_pair(-dis[y],y));}}}}intmain(){scanf("%d%d%d",&n,&m,&s);cnt=n;build(1,1,n);while(m--){intop;scanf("%d",&op);intx,y,z;llw;if(op==1){scanf("%d%d%lld",&x,&y,&z);add(x,y,z);}elseif(op==2){scanf("%d%d%d%lld",&x,&y,&z,&w);buildeg(1,x,y,z,w,0);}else{scanf("%d%d%d%lld",&x,&y,&z,&w);buildeg(1,x,y,z,w,1);}}dij();for(inti=1;i<=n;i++){if(dis[i]==inf)printf("-1");elseprintf("%lld",dis[i]);if(i!=n)printf("");}printf("\n");return0;}
