題目鏈接 第一眼就是 $KDtree$ 優化建圖
然而，空間只有 $128mb$，開不下??
時間不吃緊，考慮直接跑 $Dijkstra$
$Dijkstra$ 中存儲的是起點到每個輸入時給出的矩陣的最短距離
當取出堆頂時就將這個矩陣中所有點 "裂開"，并更新每一個小點的答案
如果該點在之前已經被一個最短路更短的矩陣更新過了，就不擴展它
否則，擴展每一個分裂出的點，將新的矩陣加入優先隊列中即可
一個重要的優化就是每次 "分裂" 一個矩陣時要在 $KDtree$ 中將對應節點都刪掉，加快下一次查詢? #include<bits/stdc++.h> #define setIO(s) freopen(s".in","r",stdin) #define maxn 2000000 #define inf 100000000 #define lson t[now].ch[0] #define rson t[now].ch[1] #define ll long long using namespace std; struct Edge { int t,x1,y1,x2,y2; Edge(int t=0,int x1=0,int y1=0,int x2=0,int y2=0):t(t),x1(x1),y1(y1),x2(x2),y2(y2){} }; struct Data { int ch[2],minv[2],maxv[2],siz,id,p[2]; }t[maxn],arr[maxn]; struct P { int dis,id; P(int dis=0,int id=0):dis(dis),id(id) {} bool operator<(P b) const {return b.dis<dis; } }; vector<int>G[maxn]; priority_queue<P>Q; vector<Edge>edges; int d,cnt,len; int dis[maxn],answer[maxn],nd[maxn],vis[maxn]; void Min(int &a,int b) { if(b<a) a=b; } void Max(int &a,int b) { if(b>a) a=b; } bool cmp(Data i,Data j) { return i.p[d]==j.p[d]?i.p[d^1]<j.p[d^1]:i.p[d]<j.p[d]; } void pushup(int now) {t[now].minv[0]=t[now].minv[1]=inf,t[now].maxv[0]=t[now].maxv[1]=-inf; for(int i=0;i<2;++i) {if(lson) {Min(t[now].minv[0],t[lson].minv[0]),Min(t[now].minv[1],t[lson].minv[1]),Max(t[now].maxv[0],t[lson].maxv[0]),Max(t[now].maxv[1],t[lson].maxv[1]); }if(rson) {Min(t[now].minv[0],t[rson].minv[0]),Min(t[now].minv[1],t[rson].minv[1]),Max(t[now].maxv[0],t[rson].maxv[0]),Max(t[now].maxv[1],t[rson].maxv[1]); }} } void build(int l,int r,int &now,int o) {now=++cnt; if(l==r) {t[now].siz=1, t[now].id=arr[l].id; t[now].p[0]=t[now].minv[0]=t[now].maxv[0]=arr[l].p[0]; t[now].p[1]=t[now].minv[1]=t[now].maxv[1]=arr[l].p[1]; return; }int mid=(l+r)>>1; d=o,nth_element(arr+l,arr+mid,arr+1+r,cmp); build(l,mid,lson,o^1); if(r>mid) build(mid+1,r,rson,o^1); pushup(now),t[now].siz=t[lson].siz+t[rson].siz; } void dfs(int now,int x1,int y1,int x2,int y2) {if(t[now].minv[0]>y1||t[now].maxv[0]<x1||t[now].minv[1]>y2||t[now].maxv[1]<x2 || !t[now].siz) return; if(t[now].id) { nd[++len]=t[now].id; t[now].siz=0; return; } if(lson) dfs(lson,x1,y1,x2,y2); if(rson) dfs(rson,x1,y1,x2,y2); t[now].siz=t[lson].siz+t[rson].siz; } void debug(int now) {if(!now) return; debug(lson), printf("%d %d %d %d\n",t[now].minv[0],t[now].maxv[0],t[now].minv[1],t[now].maxv[1]),debug(rson); } int main(){// setIO("input"); int n,m,w,h,rt; scanf("%d%d%d%d",&n,&m,&w,&h); for(int i=1;i<=n;++i) scanf("%d%d",&arr[i].p[0],&arr[i].p[1]),arr[i].id=i; build(1,n,rt,0); for(int i=1;i<=m;++i) {int a,b,c,d,e,f; scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f), edges.push_back(Edge(b,c,d,e,f)), G[a].push_back(i-1); } answer[1]=0,vis[1]=1; for(int i=0;i<G[1].size();++i) {int to=G[1][i]; dis[to]=edges[to].t, Q.push(P(edges[to].t, to)); }while(!Q.empty()) { P e=Q.top(); Q.pop();int cn=e.dis; len=1,dfs(rt, edges[e.id].x1,edges[e.id].y1,edges[e.id].x2,edges[e.id].y2); for(int i=1;i<=len;++i) { int cur=nd[i]; if(vis[cur]) continue; vis[cur]=1, answer[cur]=cn; for(int j=0;j<G[cur].size();++j) { int to=G[cur][j]; dis[to] = cn + edges[to].t; Q.push(P(dis[to], to)); }}} for(int i=2;i<=n;++i) printf("%d\n",answer[i]); return 0; }

　　

轉載于:https://www.cnblogs.com/guangheli/p/11225916.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的luogu 5471 [NOI2019]弹跳 KDtree + Dijkstra的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。