线段树优化建边的板子题
注意点到区间的连边和区间到点的连边需要两颗线段树。
点到区间连边时，由点指向区间，区间内部要从当前层向下连边，以保证点能到达区间内的每个点。
区间到点连边时，有区间指向点，区间内部要从当前层向上两边，以保证点能通过覆盖它的区间到达它能到达的点。
代码如下。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll N=4e5+10,inf=1e18;
struct node{
ll l,r,in,out;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define in(x) tree[x].in
#define out(x) tree[x].out
}tree[N*2];
ll n,m,s,cnt,vis[N],dis[N];priority_queue<pair<ll,ll> > q;vector<pair<ll,ll> > g[N];
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void build(ll p,ll l,ll r){
l(p)=l;r(p)=r;
if(l==r){in(p)=out(p)=l;return;}
in(p)=++cnt;out(p)=++cnt;
ll mid=(l+r)>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
g[in(p)].push_back(make_pair(in(p<<1),0ll));
g[in(p)].push_back(make_pair(in(p<<1|1),0ll));
g[out(p<<1)].push_back(make_pair(out(p),0ll));
g[out(p<<1|1)].push_back(make_pair(out(p),0ll));
}
inline void in_change(ll p,ll l,ll r,ll w,ll s){
if(l<=l(p)&&r(p)<=r){g[s].push_back(make_pair(in(p),w));return;}
ll mid=(l(p)+r(p))>>1;
if(l<=mid) in_change(p<<1,l,r,w,s);
if(r>mid) in_change(p<<1|1,l,r,w,s);
}
inline void out_change(ll p,ll l,ll r,ll w,ll t){
if(l<=l(p)&&r(p)<=r){g[out(p)].push_back(make_pair(t,w));return;}
ll mid=(l(p)+r(p))>>1;
if(l<=mid) out_change(p<<1,l,r,w,t);
if(r>mid) out_change(p<<1|1,l,r,w,t);
}
inline void dijkstra(){
for(ll i=1;i<=cnt;i++) dis[i]=inf;
dis[s]=0;q.push(make_pair(0,s));
while(q.size()){
ll x=q.top().second;q.pop();
if(vis[x]) continue;vis[x]=1;
for(ll i=0;i<g[x].size();i++){
ll y=g[x][i].first,z=g[x][i].second;
if(dis[y]>dis[x]+z){
dis[y]=dis[x]+z;q.push(make_pair(-dis[y],y));
}
}
}
}
int main(){
n=read();m=read();s=read();cnt=n;
build(1ll,1ll,n);
for(ll i=1;i<=m;i++){
ll k=read(),s,t,l,r,w;
if(k==1) s=read(),t=read(),w=read(),g[s].push_back(make_pair(t,w));
else if(k==2) s=read(),l=read(),r=read(),w=read(),in_change(1ll,l,r,w,s);
else if(k==3) t=read(),l=read(),r=read(),w=read(),out_change(1ll,l,r,w,t);
}
dijkstra();
for(int i=1;i<=n;i++) printf("%lld ",(dis[i]==inf)?-1:dis[i]);
return 0;
}