http://codeforces.com/problemset/problem/787/D
题目大意是给出一个有向图，有N个节点，初始节点在S，询问S到所有点最短路。边的读入方式有三种， 1 u v w 表示 u->v有一条边权为w的边， 2 v l r w ,表示v->[l,r]内的任意一个点支付w即可，
3 v l r w 表示从[l,r]内任意一个点到v支付w即可。直接构图的话可能会出现完全图，被卡死。
一种巧妙的构图方式是，由这些个区间联想到线段树(然而我并没有想到),我们不妨对2，3两种类型建立两颗线段树 他们的叶子节点是共用的(1--N)，对于2来说，如果节点v到树上的某个节点x有一条w的边，
就表示v到这个节点所对应的区间的点都可以支付w到达，并且在2的内部所有的父亲都向自己的儿子建立一条边权为0的边，这样如果v能到达x，说明v能到达x所有的子孙节点(支付w)，对于3来说只不过反过来了一下思路一样。
建完图之后跑最短路就好了，节点数大约N*10够了。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define pii pair<int,int>
#define mid ((L+R)>>1)
#define lc (id<<1)
#define rc (id<<1|1)
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f
#define linf 0xffffffffffff
const int maxn=;
int N,Q,S,T0,T1,CNT;
int ch[maxn*][];
LL d[maxn*];
bool in[maxn*];
int tot,first[maxn*];
struct Edge{int v,w,next;}e[maxn*];
void add(int u,int v,int w){
e[tot].v=v;
e[tot].w=w;
e[tot].next=first[u];
first[u]=tot++;
}
void build1(int &p,int L,int R){
if(L==R) p=L;
else{
p=++CNT;
build1(ch[p][],L,mid),build1(ch[p][],mid+,R);
add(p,ch[p][],),add(p,ch[p][],);
}
} void build2(int &p,int L,int R){
if(L==R) p=L;
else{
p=++CNT;
build2(ch[p][],L,mid),build2(ch[p][],mid+,R);
add(ch[p][],p,),add(ch[p][],p,);
}
}
void insert1(int id,int L,int R,int v,int l,int r,int w){
if(L>=l&&R<=r){
add(v,id,w);
return;
}
if(l<=mid)insert1(ch[id][],L,mid,v,l,r,w);
if(r>mid)insert1(ch[id][],mid+,R,v,l,r,w);
} void insert2(int id,int L,int R,int v,int l,int r,int w){
if(L>=l&&R<=r){
add(id,v,w);
return;
}
if(l<=mid)insert2(ch[id][],L,mid,v,l,r,w);
if(r>mid)insert2(ch[id][],mid+,R,v,l,r,w);
}
void spfa(){
for(int i=;i<=CNT;++i)d[i]=linf;
memset(in,,sizeof(in));
queue<int>q;
q.push(S);
in[S]=;
d[S]=;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=first[u];~i;i=e[i].next){
if(d[e[i].v]>d[u]+e[i].w){
d[e[i].v]=d[u]+e[i].w;
if(!in[e[i].v]){
q.push(e[i].v);
}
}
}
}
for(int i=;i<=N;++i) printf("%lld%c",d[i]==linf?-:d[i],i==N?'\n':' ');
}
int main()
{
memset(first,-,sizeof(first));
tot=;
scanf("%d%d%d",&N,&Q,&S);
CNT=N;
build1(T0,,N);
build2(T1,,N);
int opt,u,v,w,l,r;
while(Q--){
scanf("%d",&opt);
if(opt==){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
else{
scanf("%d%d%d%d",&v,&l,&r,&w);
if(opt==){
insert1(T0,,N,v,l,r,w);
}
else{
insert2(T1,,N,v,l,r,w);
}
}
}
spfa();
return ;
}
/*0 -1-112
0 -1 -1 12
*/