题解 AT5635 Shortest Path on a Line

Description

题目传送门

题面翻译

有一张有 \(N\) 个点，编号为 \(1 - N\) 的无向图。

做 \(M\) 次操作，每次操作给出三个正整数 \(L,R,C\)，对于每对 \(≥L\) 且 \(≤R\) 的整数对 \((S,T)\) ，在 \((S,T)\) 之间添加一条长度为 \(C\) 的边

完成操作后，找出操作后无向图的最短路。

数据范围

• $ N,M\ \leq\ 10^5 $

Solution

线段树优化建图裸题。

看到区间向区间连边，显然暴力处理是 \(O(MN)\) 的，时间超限。

那么可以想到处理区间问题的常用工具：线段树。

不会线段树优化建图？模板 CF786B

和模板题一样，我们先建好入树和出树。

模板题是点到区间和区间到点加边，而本题是区间向区间加边。

这个时候我们可以新建一个节点，将出树区间向这个节点连边，这个点再向入树区间连边，就转化为了模板题。

然后剩下的就是最短路板子，我用的堆优化的 Dijkstra。

Code

#include <bits/stdc++.h>
#define gc() getchar()
using namespace std;
typedef long long ll;
// 快读
template <typename T> void rd(T &x){
	T f=1;x=0;char c=gc();
	for(;!isdigit(c);c=gc())if(c=='-')f=-1;
	for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
const int MAXN=2e6+5;// 数组大小，开太小会 RE
// 链式前向星存图 
int n,m,cnt,hd[MAXN];
struct nd{
	int nxt,v,w;
}g[MAXN<<1];
inline void add(int u,int v,int w){
	g[++cnt].nxt=hd[u],g[cnt].v=v,g[cnt].w=w,hd[u]=cnt;
}
// 线段树
int tot,in[MAXN],out[MAXN];// tot 从 n 开始，in 存的是入树节点对应的图中节点编号，out 同理
struct sgt{
	int l,r;
}t[MAXN];
// 建树
inline void build(int o,int l,int r){
	t[o].l=l,t[o].r=r;
	if(l==r){
		in[o]=out[o]=l;// 如果是叶子节点，那么对应图中节点编号就是其下标，入树出树共用
		return;
	}
	int mid=l+r>>1;
	in[o]=++tot,out[o]=++tot;// 存储 o 代表的区间对应的图中节点
	build(o<<1,l,mid);
	build(o<<1|1,mid+1,r);// 递归建树
	add(out[o<<1],out[o],0);
	add(out[o<<1|1],out[o],0);// 将出树从子节点向父节点连零边
	add(in[o],in[o<<1],0);
	add(in[o],in[o<<1|1],0);// 将入树从父节点向子节点连零边
}
// 加边
inline void addedge(int o,int l,int r,int u,int w){
	if(t[o].l>=l&&t[o].r<=r){
		add(out[o],u,0);// 从出树区间向新建节点连零边
		add(u,in[o],w);// 从新建节点向入树区间连长度为 w 的边
		return;
	}
	int mid=t[o].l+t[o].r>>1;
    // 递归加边
	if(l<=mid)addedge(o<<1,l,r,u,w);
	if(r>mid)addedge(o<<1|1,l,r,u,w);
}
// Dijkstra
const ll inf=0x3f3f3f3f3f3f3f3f;
ll d[MAXN];
int vis[MAXN];
// 堆优化
struct pq{
	int v;ll w;
	pq(){}
	pq(int _v,ll _w){v=_v,w=_w;}
	bool operator<(const pq &a)const{return w>a.w;}
};
priority_queue<pq>q;
inline void dij(){
	memset(d,0x3f,sizeof(d));
	d[1]=0;q.push(pq(1,0));
	while(!q.empty()){
		pq x=q.top();q.pop();
		int u=x.v;if(vis[u])continue;
		vis[u]=1;
		for(int i=hd[u];i;i=g[i].nxt){
			int v=g[i].v,w=g[i].w;
			if(d[v]>d[u]+w)d[v]=d[u]+w,q.push(pq(v,d[v]));
		}
	}
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	rd(n),rd(m);tot=n;// tot 从 n 开始，避免与叶子节点重复
	build(1,1,n);// 别忘了建树
	for(int i=1;i<=m;++i){
		int l,r,w;
		rd(l),rd(r),rd(w);
		addedge(1,l,r,++tot,w);// ++tot 新建节点
	}
	dij();
	printf("%lld\n",d[n]==inf?-1:d[n]);// 记得开 long long
	return 0;
}

by sysong

\(2022.8.30\)