思路
线段树优化建图
基本思想就是要把一个区间连边拆成log个节点连边，
然后一颗入线段树，一颗出线段树，出线段树都由子节点向父节点连边（可以从子区间出发），入线段树从父节点向子节点连边（可以到达子区间），入线段树上每个节点向出线段树的每个对应节点连边（进来之后可以出去），题目里的边由出线段树连向入线段树
然后最短路就好了
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
int id1[800100*4],id2[800100*4],fir[800100*4],nxt[800100*4],v[800100*4],w[800100*4],lson[800100*4],rson[800100*4],root1,root2,Nodecnt,cnt,n,m,s;
void addedge(int ui,int vi,int wi){
++cnt;
v[cnt]=vi;
w[cnt]=wi;
nxt[cnt]=fir[ui];
fir[ui]=cnt;
}
void build(int l,int r,int &o1,int &o2){
o1=++Nodecnt;
o2=++Nodecnt;
addedge(o2,o1,0);
if(l==r){
id1[l]=o1;
id2[l]=o2;
return;
}
int mid=(l+r)>>1;
build(l,mid,lson[o1],lson[o2]);
build(mid+1,r,rson[o1],rson[o2]);
addedge(lson[o1],o1,0);
addedge(rson[o1],o1,0);
addedge(o2,lson[o2],0);
addedge(o2,rson[o2],0);
}
void link(int L,int R,int l,int r,int o,int opt,int v,int w){//0:[l,r]->o 1:o->[l,r]
if(L<=l&&r<=R){
if(!opt)
addedge(o,v,w);
else
addedge(v,o,w);
return;
}
int mid=(l+r)>>1;
if(L<=mid)
link(L,R,l,mid,lson[o],opt,v,w);
if(R>mid)
link(L,R,mid+1,r,rson[o],opt,v,w);
}
struct QNode{
int p,val;
bool operator < (const QNode &b) const{
return val>b.val;
}
};
priority_queue<QNode> q;
int dis[800100*4],vis[800100*4];
void dijkstra(int s){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
q.push((QNode){s,0});
while(!q.empty()){
QNode x=q.top();
q.pop();
if(vis[x.p])
continue;
vis[x.p]=true;
for(int i=fir[x.p];i;i=nxt[i]){
if(dis[v[i]]>dis[x.p]+w[i]){
dis[v[i]]=dis[x.p]+w[i];
q.push((QNode){v[i],dis[v[i]]});
}
}
}
}
signed main(){
scanf("%lld %lld %lld",&n,&m,&s);
build(1,n,root1,root2);
for(int i=1;i<=m;i++){
int opt;
scanf("%lld",&opt);
if(opt==1){
int u,v,w;
scanf("%lld %lld %lld",&u,&v,&w);
addedge(id1[u],id2[v],w);
}
else if(opt==2){
int u,l,r,w;
scanf("%lld %lld %lld %lld",&u,&l,&r,&w);
link(l,r,1,n,root2,1,id1[u],w);
}
else if(opt==3){
int l,r,v,w;
scanf("%lld %lld %lld %lld",&v,&l,&r,&w);
link(l,r,1,n,root1,0,id2[v],w);
}
}
dijkstra(id2[s]);
for(int i=1;i<=n;i++)
printf("%lld ",dis[id1[i]]==0x3f3f3f3f3f3f3f3fLL?-1:dis[id1[i]]);
return 0;
}