题意
有n个点，q个询问，每次询问有一种操作。操作1：u→[l,r]（即u到l，l+1，l+2，...，r距离均为w）的距离为w；操作2：[l,r]→u的距离为w；操作3：u到v的距离为w；求起点到其他点的最短距离，到达不了输出-1。
题解
线段树骚操作，线段树优化建图。
其实提到可以这么操作后，实现还是很好想的。
建两颗线段树，一颗连进边，一颗连出边。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 const int N=100010; 9 const long long INF=999999999999999; 10 int cnt,head[N*40]; 11 struct tree{ 12 int l,r; 13 }tr[N*40]; 14 int ch[N*40][2]; 15 long long dis[N*40]; 16 int book[N*40]; 17 int n,m,s,tot,root1,root2; 18 struct edge{ 19 int to,nxt,w; 20 }e[N*100]; 21 void add(int u,int v,int w){ 22 cnt++; 23 e[cnt].nxt=head[u]; 24 head[u]=cnt; 25 e[cnt].to=v; 26 e[cnt].w=w; 27 } 28 void build1(int l,int r,int &now){ 29 if(l==r){ 30 now=l; 31 tr[now].l=tr[now].r=l; 32 return; 33 } 34 now=++tot; 35 tr[now].l=l;tr[now].r=r; 36 int mid=(l+r)>>1; 37 build1(l,mid,ch[now][0]); 38 build1(mid+1,r,ch[now][1]); 39 add(now,ch[now][0],0); 40 add(now,ch[now][1],0); 41 } 42 void build2(int l,int r,int &now){ 43 if(l==r){ 44 now=l; 45 tr[now].l=tr[now].r=l; 46 return; 47 } 48 now=++tot; 49 tr[now].l=l;tr[now].r=r; 50 int mid=(l+r)>>1; 51 build2(l,mid,ch[now][0]); 52 build2(mid+1,r,ch[now][1]); 53 add(ch[now][0],now,0); 54 add(ch[now][1],now,0); 55 } 56 void link(int l,int r,int now,int node,int k,int c){ 57 if(tr[now].l>=l&&tr[now].r<=r){ 58 if(k==1)add(node,now,c); 59 else add(now,node,c); 60 return; 61 } 62 int mid=(tr[now].l+tr[now].r)>>1; 63 if(l>mid)link(l,r,ch[now][1],node,k,c); 64 else if(r<=mid)link(l,r,ch[now][0],node,k,c); 65 else{ 66 link(l,mid,ch[now][0],node,k,c); 67 link(mid+1,r,ch[now][1],node,k,c); 68 } 69 } 70 void spfa(){ 71 for(int i=1;i<=tot;i++){ 72 dis[i]=INF; 73 } 74 queue<int> q; 75 q.push(s); 76 dis[s]=0; 77 book[s]=1; 78 while(!q.empty()){ 79 int u=q.front(); 80 q.pop(); 81 book[u]=0; 82 for(int i=head[u];i;i=e[i].nxt){ 83 int v=e[i].to; 84 if(dis[v]>dis[u]+e[i].w){ 85 dis[v]=dis[u]+e[i].w; 86 if(book[v]==0){ 87 book[v]=1; 88 q.push(v); 89 } 90 } 91 } 92 } 93 } 94 int main(){ 95 scanf("%d%d%d",&n,&m,&s); 96 tot=n; 97 build1(1,n,root1); 98 build2(1,n,root2); 99 for(int i=1;i<=m;i++){ 100 int k; 101 scanf("%d",&k); 102 if(k==1){ 103 int u,v,w; 104 scanf("%d%d%d",&u,&v,&w); 105 add(u,v,w); 106 } 107 else if(k==2){ 108 int u,l,r,w; 109 scanf("%d%d%d%d",&u,&l,&r,&w); 110 link(l,r,root1,u,1,w); 111 } 112 else{ 113 int v,l,r,w; 114 scanf("%d%d%d%d",&v,&l,&r,&w); 115 link(l,r,root2,v,2,w); 116 } 117 } 118 spfa(); 119 for(int i=1;i<=n;i++){ 120 if(dis[i]==INF)printf("-1 "); 121 else printf("%lld ",dis[i]); 122 } 123 return 0; 124 }