前言
板题二号？
题目
讲解
可以发现这个就是K-D树优化最短路建图板题？
K-D树上的点对应一个矩形区间，当然还有平凡的 \(n\) 个点就表示单点。
然后跑 dijkstra，因为 dijkstra 的点只会出队一次，所以其实挺快的。
注意这道题卡空间，所以我们不能显示地把图建出来，要在 dijkstra 过程中在线求。
交洛谷，过了，交 UOJ，T了。十分疑惑，于是去 U群问：
很快 EI 就回复我了：
那没办法了啊，人家专门卡的。(现在知道我为什么前面打问号了吧)
于是老师换了个链接，改成 LOJ，我就拿到了一血。/xyx
不是很会算时间复杂度。
代码
LOJ要freopen
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 70005 << 1;
const int INF = 0x3f3f3f3f;
int n,m,w,h,dis[MAXN];
int nxt[2] = {1,0};
bool vis[MAXN];
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
struct tec{int t,L,R,D,U;}cur;
vector<tec> G[MAXN];
struct spot
{
int x,d;
bool operator < (const spot &px)const{
return d > px.d;
}
}tmp;
priority_queue<spot> q;
int tot,rt,mode;
struct point{int x,y;};
bool operator < (point A,point B){if(!mode) return A.x < B.x;return A.y < B.y;}
struct Info{point p;int ID;}c[MAXN];
bool operator < (Info A,Info B){return A.p < B.p;}
#define lc t[x].ch[0]
#define rc t[x].ch[1]
struct node
{
Info info;
point l,r;
int ch[2];
}t[MAXN];
void up1(int x,int son)
{
if(!son) return;
t[x].l.x = Min(t[x].l.x,t[son].l.x);
t[x].l.y = Min(t[x].l.y,t[son].l.y);
t[x].r.x = Max(t[x].r.x,t[son].r.x);
t[x].r.y = Max(t[x].r.y,t[son].r.y);
}
void up(int x)
{
t[x].l = t[x].r = t[x].info.p;
up1(x,lc); up1(x,rc);
}
void Build(int &x,int l,int r,int now)
{
x = ++tot; mode = now;
int mid = (l+r) >> 1;
nth_element(c+l,c+mid,c+r+1);
t[x].info = c[mid];
if(l < mid) Build(lc,l,mid-1,nxt[now]);
if(mid < r) Build(rc,mid+1,r,nxt[now]);
up(x);
}
int nowdis;
void inq(int x,int d){if(d < dis[x]) q.push(spot{x,dis[x] = d});}
void Add_Edge(int x)
{
if(vis[x]) return;
if(cur.L <= t[x].l.x && t[x].r.x <= cur.R && cur.D <= t[x].l.y && t[x].r.y <= cur.U)
{inq(x,nowdis); return;}
if(cur.L <= t[x].info.p.x && t[x].info.p.x <= cur.R && cur.D <= t[x].info.p.y && t[x].info.p.y <= cur.U)
inq(t[x].info.ID,nowdis);
if(t[x].l.x > cur.R || t[x].r.x < cur.L || t[x].l.y > cur.U || t[x].r.y < cur.D) return;
if(lc) Add_Edge(lc);
if(rc) Add_Edge(rc);
}
int main()
{
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
n = Read(); m = Read(); w = Read(); h = Read();
for(int i = 1;i <= n;++ i) c[i].p.x = Read(),c[i].p.y = Read(),c[i].ID = i;
for(int i = 1;i <= m;++ i)
{
int pos = Read(),t = Read(),L = Read(),R = Read(),D = Read(),U = Read();
G[pos].emplace_back(tec{t,L,R,D,U});
}
tot = n; Build(rt,1,n,0);
for(int i = 1;i <= tot;++ i) dis[i] = INF;
q.push(spot{1,dis[1] = 0});
while(!q.empty())
{
tmp = q.top(); q.pop(); int x = tmp.x;
if(tmp.d > dis[x]) continue;
vis[x] = 1;
if(x <= n)
{
for(int i = 0,len = G[x].size();i < len;++ i)
cur = G[x][i],nowdis = dis[x]+cur.t,Add_Edge(rt);
}
else
{
nowdis = dis[x];
inq(t[x].info.ID,nowdis);
if(lc) inq(lc,nowdis);
if(rc) inq(rc,nowdis);
}
}
for(int i = 2;i <= n;++ i) Put(dis[i],'\n');
return 0;
}