题目大意
一开始有 \(n\) 个点，有 \(m\) 个操作，每个操作是以下三种之一：
- 连边 \(i\to j\)，边权为 \(w\);
- 对于所有 \(i\in [l,r]\)，连边 \(i\to j\)，边权为 \(w\)；
- 对于所有 \(j\in [l,r]\)，连边 \(i\to j\)，边权为 \(w\)。
所有操作进行完后问你从 \(s\) 到所有点的最短路。
\(1\le n,m\le 10^5\)。
题解
对于操作一，直接连即可。
对于操作二，建一棵类似于线段树之类的东西，其中的每个点都代表一个区间，同时每个点向其父节点连边（因为某个区间向 \(1\dots n\) 中的某个点连边，就相当于其所有子区间都向这个点连边）。对于线段树中的叶子节点，从它对应的原节点向其连边。将操作中的区间 \([l,r]\) 拆成 线段树上的 \(\log n\) 个区间，这些区间都向这个点连边即可。
对于操作三同理，建一棵反向的线段树即可。
建完图跑一边最短路，时间复杂度 \(O(n \log n \log (n \log n))=O(n\log^2 n)\)。
计算一下这张图中点和边的个数：每棵线段树有 \(4n\) 个点，原图中有 \(n\) 个点，因此点数是 \(9n\)；每棵线段树约有 \(4n\) 条边，线段树的叶子节点会连 \(n\) 个边，每次操作最多连 \(\log n\) 条边，于是总边数是 \(10n+m\log n\)。
代码
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
typedef long long ll;
template<typename T> void Read(T &x){
x=0;int f=1,ch;
for(ch=getchar();!isdigit(ch);ch=getchar()) f=(ch=='-'?-1:1);
for(;isdigit(ch);ch=getchar()) x=x*10+(ch-48);
x*=f;
}
template<typename T,typename... Args> void Read(T &x,Args&... args){
Read(x);Read(args...);
}
const int N=1e5+5;
const ll Infll=0x3f3f3f3f3f3f3f3fLL;
int n,q,s,tot=0,num[N];
int head[N*10],cntt=0;
struct Edge{int v,nxt;ll w;}e[int(3e6+5)];
void AddEdge(int u,int v,ll w){
e[++cntt]=Edge{v,head[u],w};head[u]=cntt;
}
struct Segtree{
#define ls(xx) ((xx)<<1)
#define rs(xx) ((xx)<<1|1)
int dir;
struct Node{
int l,r,v;
}t[N<<2];
Segtree(int dir_):dir(dir_){}
void Build(int p,int l,int r){
t[p].l=l,t[p].r=r,t[p].v=++tot;
if(l==r){
if(~dir) AddEdge(t[p].v,num[l],0);
else AddEdge(num[l],t[p].v,0);
return;
}
int mid=(l+r)>>1;
Build(ls(p),l,mid);
if(~dir) AddEdge(t[p].v,t[ls(p)].v,0);
else AddEdge(t[ls(p)].v,t[p].v,0);
Build(rs(p),mid+1,r);
if(~dir) AddEdge(t[p].v,t[rs(p)].v,0);
else AddEdge(t[rs(p)].v,t[p].v,0);
}
void Add(int p,int l,int r,int x,ll w){
if(l<=t[p].l&&t[p].r<=r){
if(~dir) AddEdge(num[x],t[p].v,w);
else AddEdge(t[p].v,num[x],w);
return;
}
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) Add(ls(p),l,r,x,w);
if(r>mid) Add(rs(p),l,r,x,w);
}
}tr1(1),tr2(-1);
ll dis[N*10];
void Dijkstra(){
static int hp[N*10];int len=0;
auto Cmp=[](int i,int j){return dis[i]>dis[j];};
memset(dis,0x3f,sizeof(ll)*(tot+2));
hp[++len]=num[s],dis[num[s]]=0;push_heap(hp+1,hp+len+1,Cmp);
while(len){
pop_heap(hp+1,hp+len+1,Cmp);
int u=hp[len--];
for(int i=head[u];i;i=e[i].nxt){
if(dis[e[i].v]>dis[u]+e[i].w){
dis[e[i].v]=dis[u]+e[i].w;
hp[++len]=e[i].v;
push_heap(hp+1,hp+len+1,Cmp);
}
}
}
}
int main(){
Read(n,q,s);
For(i,1,n) num[i]=++tot;
tr1.Build(1,1,n),tr2.Build(1,1,n);
int op,v,l,r,w;
For(i,1,q){
Read(op);
if(op==1){
Read(l,r,w);AddEdge(num[l],num[r],w);
}else if(op==2){
Read(v,l,r,w);
tr1.Add(1,l,r,v,w);
}else if(op==3){
Read(v,l,r,w);
tr2.Add(1,l,r,v,w);
}
}
Dijkstra();
For(i,1,n){
if(dis[num[i]]!=Infll) printf("%lld ",dis[num[i]]);
else printf("-1 ");
}
return 0;
}