题意
现有一个图,有 \(n\) 个节点,从节点 \(s\) 出发,求到 \(n\) 个点每一个点的最短路。
其中,有三种建边方式 :
-
建一条从 \(u\) 到 \(v\) 的单向边。
-
从节点 \(v\) 分别向 \([l,r]\) 的每个结点连一条边。
-
从节点 \([l,r]\) 向节点 \(v\) 连边
芝士
线段树优化 \(dijstra\)
思路
观察数据范围,发现如果全部按照普通 \(dijstra\) 的建图方法来做的话,会TLE。
因此,可以发现需要优化建图,而通读了题面,发现恰好是区间的操作使得我们的时间不够用,于是可以想到用线段树优化 \(dijstra\) 。
具体实现
- 建树
-
在使用线段树优化 \(dijstra\) 时,需要两个树,一个是出,一个是入,所以每一条边都应为单向边。
-
其中每一个树上的每一条边的边权都为 \(0\) 。
-
应在两棵树上节点序号相同的两个点之间连一条边权为 \(0\) 双向边,因为这两个点本来就是同一个(或是一些)星球。
-
在我的做法中我将两个线段树都放入了一个数组中,并将 \(K\) (常量,根据数据范围算出)表示为一颗线段树最大的大小,因此,上文中两棵树上相同序号的点在我的写法中分别为 \(i\) 与 \(i+K\) 。
-
需要在建树时预处理出所有单个星球在线段树上对应的节点编号,并储存下来,这里使用 \(a_i\) 来表示星球 \(i\) 在(编号较小的那颗)线段树上对应的节点编号。对应的,在编号较大的那颗线段树上所对应的编号应为 \(a_i+K\) 。
- 建边
(vector好耶)
-
第一种就是普通的建边,将 \(a_v\) 与 \(a_u\) 连一条单向边。
-
第二种和第三种就是使用 \(update\) 在线段树上找到可以代表 \([l,r]\) 区间内的所有星球的一些点,并与另一棵树上的代表 \(v\) 的叶子节点建边。
- 跑 \(dijstra\) 时
- 就普通地跑。
tips
-
注意\(a_i\) 与 \(i\) 的区别
-
注意区分出树和入树。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,q,s,K=4e5+5;
int tr[MAXN*8],vis[MAXN*8],a[MAXN*8];
long long d[MAXN*8];
vector<int>vec[MAXN*8],val[MAXN*8];
void add(int u,int v,int d){//建边
vec[u].push_back(v);
val[u].push_back(d);
return ;
}
void build(int rt,int l,int r){
if(l==r){
a[l]=rt;
add(a[l],a[l]+K,0);
add(a[l]+K,a[l],0);//同一个星球,建双向边
return ;
}
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
add(rt,rt<<1,0),add(rt,rt<<1|1,0);//相邻的节点,建单向边(父节点与子节点)
add((rt<<1)+K,rt+K,0),add((rt<<1|1)+K,rt+K,0);
}
void update(int rt,int l,int r,int L,int R,int w,int u){//第二和三种建边
if(L<=l && R>=r){
if(u<=K){
add(rt+K,u,w);
}
else{
add(u,rt,w);
}
return ;
}
int mid=l+r>>1;
if(mid>=L){
update(rt<<1,l,mid,L,R,w,u);
}
if(R>mid){
update(rt<<1|1,mid+1,r,L,R,w,u);
}
return ;
}
struct node{
int v;
long long d;
bool operator<(const node &a)const{
return d>a.d;
}
};
void dij(){//最最最普通的最短路
priority_queue<node>q;
q.push(node{s,0});
d[s]=0;
while(!q.empty()){
int u=q.top().v;
long long di=q.top().d;
q.pop();
if(vis[u]){
continue;
}
vis[u]=1;
for(int i=0;i<vec[u].size();i++){
int v=vec[u][i],dis=val[u][i];
if(di+dis<d[v]){
d[v]=di+dis;
q.push(node{v,d[v]});
}
}
}
}
int main(){
cin>>n>>q>>s;
build(1,1,n);
while(q--){
int opt;
cin>>opt;
if(opt==1){
int u,v,w;
cin>>u>>v>>w;
add(a[u],a[v],w);//注意这里是a[u]和a[v]而非u和v
}
else{
int u,l,r,w;
cin>>u>>l>>r>>w;
update(1,1,n,l,r,w,a[u]+K*(opt==2));
}
}
memset(d,0x3f,sizeof(d));
s=a[s]+K;
dij();
for(int i=1;i<=n;i++){
if(d[a[i]]==0x3f3f3f3f3f3f3f3f){//注意特判
cout<<-1<<" ";
continue;
}
cout<<d[a[i]]<<" ";
}
}
结语
只是彩笔博主瞎掰扯,他自己都看不懂自己在干什么,欢迎指出博主的问题靴靴qaq。
被数据结构薄纱了
标签:int,题解,线段,dijstra,MAXN,建边,CF786B,节点 From: https://www.cnblogs.com/Le-Louvre/p/18408660