题意：
给你平面上的$n$个点，共有$m$个弹跳装置。
每个弹跳装置可以从点$p_{i}$以$t_{i}$的代价跳到矩形$(L_{i},D_{i}),(R_{i},U_{i})$中的任何一个点。
现在请你对于每座城市求出从1号点跳到它的最小代价。
$n\leq 70000,m\leq 150000$。
题解：
看一眼就知道$KD-tree$优化建图，但如果把所有边都建出来就$MLE$了。
设原图上的点是实点，$KD-tree$上的点（代表一个实点和一个矩形）是虚点。
那么在$Dijkstra$到每个点的时候：
- 若是实点，在$KD-tree$上查找能连的虚点/实点并向其连带权边。
- 若是虚点，向它的两个儿子和它对应的实点连权为0的边。
时间复杂度$O(m\sqrt{n})$，空间复杂度$O(m)$（实际上只有优先队列可能达到这个空间，其他都是$O(n)$）。
没了。不知道为什么有人写线段树。
代码：
#include<bits/stdc++.h> #define maxn 200005 #define maxm 500005 #define inf 0x7fffffff #define ll long long #define rint register int #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; struct Point{int x[2],iid;}p[maxn]; int mx[maxn][2],mn[maxn][2],id[maxn],ls[maxn],rs[maxn]; int tot,np,dis[maxn<<1],vis[maxn<<1],tim[maxn]; int L[maxn],R[maxn],D[maxn],U[maxn]; struct node{int u,d;bool operator<(const node &b)const{return d>b.d;}}; priority_queue<node> q; vector<int> vc[maxn]; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline node md(int u,int d){node res;res.u=u,res.d=d;return res;} inline void upd(int u,int v){if(dis[u]>v){dis[u]=v,q.push(md(u,v));}} inline bool ok(int xa,int ya,int xb,int yb){return xb<=xa&&ya<=yb;} inline bool cmp(Point a,Point b){return (!np)?(a.x[0]<b.x[0]):(a.x[1]<b.x[1]);} inline void pushup(int k){ for(rint i=0;i<2;i++){ mx[k][i]=mn[k][i]=p[id[k]].x[i]; if(ls[k]) mx[k][i]=max(mx[k][i],mx[ls[k]][i]),mn[k][i]=min(mn[k][i],mn[ls[k]][i]); if(rs[k]) mx[k][i]=max(mx[k][i],mx[rs[k]][i]),mn[k][i]=min(mn[k][i],mn[rs[k]][i]); } } inline int build(int l,int r,int type){ if(l>r) return 0; int mid=l+r>>1,k=++tot; id[k]=mid,np=type; nth_element(p+l,p+mid,p+r+1,cmp); ls[k]=build(l,mid-1,type^1); rs[k]=build(mid+1,r,type^1); pushup(k); return k; } inline void add(int l,int r,int d,int u,int c,int k){ //cout<<k<<":"<<mn[k][0]<<" "<<mx[k][0]<<" "<<mn[k][1]<<" "<<mx[k][1]<<endl; if(mx[k][0]<l || mn[k][0]>r || mx[k][1]<d || mn[k][1]>u) return; if(ok(mn[k][0],mx[k][0],l,r)&&ok(mn[k][1],mx[k][1],d,u)){upd(k,c);return;} if(ok(p[id[k]].x[0],p[id[k]].x[0],l,r)&&ok(p[id[k]].x[1],p[id[k]].x[1],d,u)) upd(p[id[k]].iid,c); if(ls[k]) add(l,r,d,u,c,ls[k]); if(rs[k]) add(l,r,d,u,c,rs[k]); return; } inline void Dijkstra(int s,int n){ memset(vis,0,sizeof(vis)); memset(dis,127,sizeof(dis)); dis[s]=0,q.push(md(s,0)); while(!q.empty()){ rint u=q.top().u; q.pop(); if(vis[u]) continue; vis[u]=1; //cout<<u<<":"<<dis[u]<<" "<<vc[u].size()<<endl; if(u<=n) for(rint i=0;i<vc[u].size();i++) add(L[vc[u][i]],R[vc[u][i]],D[vc[u][i]],U[vc[u][i]],dis[u]+tim[vc[u][i]],n+1); else upd(p[id[u]].iid,dis[u]),upd(ls[u],dis[u]),upd(rs[u],dis[u]); } } int main(){ freopen("jump.in","r",stdin); freopen("jump.out","w",stdout); int n=read(),m=read(),w=read(),h=read(); for(rint i=1;i<=n;i++) p[i].x[0]=read(),p[i].x[1]=read(),p[i].iid=i; tot=n,build(1,n,0); for(rint i=1;i<=m;i++){ int p=read();tim[i]=read(); L[i]=read(),R[i]=read(); D[i]=read(),U[i]=read(); vc[p].push_back(i); } Dijkstra(1,n); for(rint i=2;i<=n;i++) printf("%d\n",dis[i]); return 0; }