问题：
CF786B
给定一个\(n\)个点，\(m\)次连边的有向图，有三种连边（均有边权）方式：
1.\(u\to v\)，一条\(u\)指向\(v\)的连边。
2.\(u\to [l,r]\)，\(u\)向在区间\([l,r]\)的点分别连一条边。
3.\([l,r]\to v\)，在区间\([l,r]\)的点向\(v\)分别连一条边。
问从\(1\)点出发，到各个点的最短路。
思路:
这里是用线段树优化建图trick，就是如果每次2和3的操作\([l,r]\)都是\([1,n]\)，建边的数量就是\(n\times m\)。这里类比求区间和，可以使用线段树，将一个点向一个线段树上的点连边，每次连\(\log_{2} n\)条边。线段树上的点再连上它在线段树上的子节点，叶子节点就直接连图上的对应点，就能与2和3操作等效。注意：要建一棵自上而下的线段树和一颗自下而上的线段树。
代码:
#include<iostream>
#include<vector>
#include<queue>
#define int long long
#define INF 1000000000000000000
using namespace std;
int kd(){
int x=0,f=1;
char a=getchar();
while(a<'0'||a>'9'){
if(a=='-'){
f=-1;
}
a=getchar();
}
while(a>='0'&&a<='9'){
x=x*10+a-'0';
a=getchar();
}
return x*f;
}
int n,q,s;
struct node{
int l,r;
}tree[400010];
struct nod{
int to;
int nxt;
int val;
}edge[4000010];
int head[1000010],tot;
void addedge(int u,int v,int w){
edge[++tot].to=v;
edge[tot].nxt=head[u];
edge[tot].val=w;
head[u]=tot;
}
void build(int i,int l,int r){
tree[i].l=l;
tree[i].r=r;
if(l==r){
addedge(i,l+8*n,0);
addedge(l+8*n,i+4*n,0);
return ;
}
int mid=(l+r)/2;
addedge(i,i*2,0);
addedge(i,i*2+1,0);
addedge(i*2+4*n,i+4*n,0);
addedge(i*2+1+4*n,i+4*n,0);
build(i*2,l,mid);
build(i*2+1,mid+1,r);
return ;
}
void search1(int i,int l,int r,int k,int w){
if(tree[i].l>=l&&tree[i].r<=r){
addedge(k+8*n,i,w);
return ;
}
if(tree[i*2].r>=l){
search1(i*2,l,r,k,w);
}
if(tree[i*2+1].l<=r){
search1(i*2+1,l,r,k,w);
}
}
void search2(int i,int l,int r,int k,int w){
if(tree[i].l>=l&&tree[i].r<=r){
addedge(i+4*n,k+8*n,w);
return ;
}
if(tree[i*2].r>=l){
search2(i*2,l,r,k,w);
}
if(tree[i*2+1].l<=r){
search2(i*2+1,l,r,k,w);
}
}
int dis[1000010];
bool vis[1000010];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > dui;
void dij(){
dui.push(make_pair(0,8*n+s));
while(!dui.empty()){
int u=dui.top().second;
dui.pop();
if(vis[u]==1){
continue;
}
vis[u]=1;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(vis[v]==1){
continue;
}
if(dis[v]>dis[u]+edge[i].val){
dis[v]=dis[u]+edge[i].val;
dui.push(make_pair(dis[v],v));
}
}
}
}
signed main(){
cin>>n>>q>>s;
build(1,1,n);
while(q--){
int opt;
opt=kd();
if(opt==1){
int u,v,w;
u=kd();v=kd();w=kd();
addedge(u+8*n,v+8*n,w);
}
if(opt==2){
int u,l,r,w;
u=kd();l=kd();r=kd();w=kd();
search1(1,l,r,u,w);
}
if(opt==3){
int v,l,r,w;
v=kd();l=kd();r=kd();w=kd();
search2(1,l,r,v,w);
}
}
for(int i=1;i<=9*n;i++){
dis[i]=INF;
}
dis[8*n+s]=0;
dij();
for(int i=1;i<=n;i++){
if(dis[8*n+i]==INF){
printf("-1 ");
}
else{
printf("%lld ",dis[8*n+i]);
}
}
return 0;
}