题目链接
https://www.luogu.com.cn/problem/P5471
题解
测试点 1-13
这些测试点中，暴力连边跑最短路的时间和空间复杂度（当然前提是你得用最坏复杂度可以通过的最短路算法）可以接受。
建图的时间复杂度：
- 测试点 \(1 \sim 8\)：\(O(n^2)\)；
- 测试点 \(9 \sim 13\)：\(O(n \log n)\)。
测试点 14-18
平面退化成了直线，而我们连边总是从某个点连向在某个区间内的所有点。考虑使用线段树优化建图。
我们先建出线段树，其中树上的每个点向其两个子节点各连一条边权为 \(0\) 的边，每个叶子节点向其对应的真实节点连一条边权为 \(0\) 的边。
建图的方式和线段树维护区间信息差不多，我们只需向线段树上能覆盖对应区间的点连边即可。和线段树维护区间信息一样，我们一次最多连 \(O(\log n)\) 条边。
因此我们连的总边数为 \(O(n+m \log n)\)。
满分做法
现在考虑二维平面上的问题。
考虑在线段树套线段树上建图。和一维的情况类似，我们先在外层查询满足 \(x\) 范围的点，再在内层查询满足 \(y\) 范围的点来建图即可。
树套树的空间复杂度为：\(O(n \log^2 n)\)。连边的总数为 \(O(m \log^2 n)\)。因为本题空间限制较小，上面的做法无法通过本题。
如何优化空间？
可以将内层的线段树换成 set。从而数据结构的空间复杂度为 \(O(n \log n)\)。
更棒的是，我们实际上可以不将边连出来，从而省下了建图的空间。
不建图怎么求最短路？直接利用已有的弹跳装置的信息来更新最短路。
我们回想一下 Dijkstra 求最短路的性质。我们每次从堆顶取出的点，其最短路已经是确定的，不会再更新。
设从 \(1\) 号点经过第 \(i\) 个弹跳装置的最短路为 \(w_i\)，我们先将从 \(1\) 开始的所有装置扔进堆里。
从堆中取出 \(w_i\) 最小的装置（根据上文所述，这个装置的 \(w_i\) 不会再更新），在线段树套 set 里查询当前装置能到达的点，将这些点的最短路更新为 \(w_i\)，随后将这些点从数据结构里删除（根据上面的描述，这些点的最短路不会再更新）。与此同时，我们更新经过当前装置能直接到达的装置的 \(w_i\) 值。
#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
struct point
{
int x,y,id;
bool operator<(const point&a)const
{
return y<a.y||(y==a.y&&x<a.x);
}
}p[70005];
struct edge
{
int p,t,l,r,d,u;
}e[150005];
struct node
{
int u,dis;
bool operator>(const node&a)const
{
return dis>a.dis;
}
};
vector<int> f[70005];
set<point> s[300005];
priority_queue<node,vector<node>,greater<node> > q;
int dis[70005],vis[150005];
int n,m,w,h;
void add(int root,int l,int r,int x)
{
s[root].insert(p[x]);
if(l==r)return;
int mid=(l+r)>>1;
if(p[x].x<=mid)add(root<<1,l,mid,x);
else add(root<<1|1,mid+1,r,x);
}
void del(int root,int l,int r,int x)
{
s[root].erase(p[x]);
if(l==r)return;
int mid=(l+r)>>1;
if(p[x].x<=mid)del(root<<1,l,mid,x);
else del(root<<1|1,mid+1,r,x);
}
void modify(int root,int cl,int cr,int x,int d)
{
queue<int> dq;
int l=e[x].l,r=e[x].r;
if(cr<l||r<cl)return;
if(l<=cl&&cr<=r)
{
auto it=s[root].lower_bound((point){0,e[x].d,0});
//在线段树套 set 里找每个装置能到达的点
for(;it!=s[root].end()&&it->y<=e[x].u;it++)
{
int u=it->id;
dis[u]=d;//更新这些点的最短路
dq.push(u);
for(auto v:f[u])//将经过当前装置能到达的下一个装置插入堆
q.push({v,d+e[v].t});
}
while(!dq.empty())//将这些点从数据结构中删除
{
int u=dq.front();
dq.pop();
del(1,1,n,u);
}
return;
}
int mid=(cl+cr)>>1;
modify(root<<1,cl,mid,x,d);
modify(root<<1|1,mid+1,cr,x,d);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>w>>h;
for(int i=1;i<=n;i++)
{
cin>>p[i].x>>p[i].y;
p[i].id=i;
add(1,1,n,i);//将所有点扔进线段树套 set 里
}
for(int i=1;i<=m;i++)
{
cin>>e[i].p>>e[i].t>>e[i].l>>e[i].r>>e[i].d>>e[i].u;
f[e[i].p].push_back(i);//维护从 i 号点出发的装置列表
}
e[0].l=e[0].r=p[1].x;
e[0].d=e[0].u=p[1].y;
q.push({0,0});
while(!q.empty())
{
int u=q.top().u,d=q.top().dis;
q.pop();
if(vis[u])continue;//和 Dijkstra 一样，已经走过的装置不必再走
vis[u]=1;
modify(1,1,n,u,d);
}
for(int i=2;i<=n;i++)
cout<<dis[i]<<endl;
return 0;
}