题意：
题解：
其实这个做法似乎并不是真的，在uoj上被卡了97分。但是没有关系，至少它是能在官方数据下AC的。
这题做法十分清晰，直接建图跑最短路显然会T飞，那么我们可以考虑用数据结构优化建图，也就是点向数据结构连边，然后数据结构再向点连边，利用数据结构优化边数。
考虑使用二维线段树优化。为什么是假的，因为我采用了四叉树。对于一个弹跳装置，向它对应的线段树连边，然后对与每一个线段树节点，向自己所管辖的城市连边，然后跑dijkstra+堆优化就可以了。
然后就得到又TLE又MLE的好成绩。其实我们不需要连边，弹跳装置连线段数的边太多了，干脆不连了，直接在线段树上寻找对应节点即可。反正每个点在dij中只会被跑一次。这样就不会MLE了，然而会TLE，因为边还是太多了，需要优化。
优化很简单，在线段树上跑的时候，如果从dij的优先队列中拿出来点的最短路+边权已经比当前线段树上的节点的最短路来的大了，那么不用往下跑了，因为它不可能再更新其它点了，直接return即可。然后就水过去了
#include<cstdio> #include<bitset> #include<queue> #include<vector> #include<algorithm> #include<cstdlib> using namespace std; const int INF=1e9; int n,m,w,h,x[70002],y[70002],d[4000002],cnt,beg[70002]; bitset<4000002>fl; typedef struct{ int x,d; }PP; bool operator<(const PP& aa,const PP& bb){ return aa.d>bb.d; } priority_queue<PP>t; typedef struct{ int p,t,l,r,d,u; }Q; typedef struct{ int s[4],lx,rx,ly,ry; }P; typedef struct{ int y,num; }GG; bool cmpp(const GG& aa,const GG& bb){ return aa.y<bb.y; } P p[2000002]; Q q[150002]; vector<GG>g[70002]; bool cmp(Q aa,Q bb){ return (aa.p<bb.p); } int ef(int x,int z){ int lef=0,righ=g[x].size()-1,mid; while(lef<righ) { mid=(lef+righ)/2; if (g[x][mid].y<z)lef=mid+1;else righ=mid; } return lef; } bool pd(int lx,int rx,int ly,int ry){ int x; for (int i=lx;i<=rx;i++) { if (!g[i].size())continue; x=ef(i,ly); if (g[i][x].y>=ly && g[i][x].y<=ry)return 1; } return 0; } void build(int root,int lx,int rx,int ly,int ry){ p[root-n].lx=lx;p[root-n].rx=rx;p[root-n].ly=ly;p[root-n].ry=ry; if (lx==rx && ly==ry)return; int m1=(lx+rx)/2,m2=(ly+ry)/2; if (lx<=m1 && ly<=m2 && pd(lx,m1,ly,m2)) { p[root-n].s[0]=++cnt;build(cnt,lx,m1,ly,m2); } if (lx<=m1 && m2+1<=ry && pd(lx,m1,m2+1,ry)) { p[root-n].s[1]=++cnt;build(cnt,lx,m1,m2+1,ry); } if (m1+1<=rx && ly<=m2 && pd(m1+1,rx,ly,m2)) { p[root-n].s[2]=++cnt;build(cnt,m1+1,rx,ly,m2); } if (m1+1<=rx && m2+1<=ry && pd(m1+1,rx,m2+1,ry)) { p[root-n].s[3]=++cnt;build(cnt,m1+1,rx,m2+1,ry); } } void gengxin(int root,int lx,int rx,int ly,int ry,int lx2,int rx2,int ly2,int ry2,int dd,int tt){ if (!root || lx>rx2 || rx<lx2 || ly>ry2 || ry<ly2 || d[root]<dd+tt)return; if (lx>=lx2 && rx<=rx2 && ly>=ly2 && ry<=ry2) { if (dd+tt<d[root]) { d[root]=dd+tt;PP aa; aa.x=root;aa.d=d[root]; t.push(aa); } return; } int m1=(lx+rx)/2,m2=(ly+ry)/2; gengxin(p[root-n].s[0],lx,m1,ly,m2,lx2,rx2,ly2,ry2,dd,tt); gengxin(p[root-n].s[1],lx,m1,m2+1,ry,lx2,rx2,ly2,ry2,dd,tt); gengxin(p[root-n].s[2],m1+1,rx,ly,m2,lx2,rx2,ly2,ry2,dd,tt); gengxin(p[root-n].s[3],m1+1,rx,m2+1,ry,lx2,rx2,ly2,ry2,dd,tt); } int main() { scanf("%d%d%d%d",&n,&m,&w,&h);cnt=n; for (int i=1;i<=n;i++) { scanf("%d%d",&x[i],&y[i]);GG aa;aa.y=y[i];aa.num=i; g[x[i]].push_back(aa);beg[i]=INF; } for (int i=1;i<=m;i++)scanf("%d%d%d%d%d%d",&q[i].p,&q[i].t,&q[i].l,&q[i].r,&q[i].d,&q[i].u); for (int i=1;i<=w;i++)sort(g[i].begin(),g[i].end(),cmpp); cnt++;build(cnt,1,w,1,h);sort(q+1,q+m+1,cmp); for (int i=1;i<=m;i++)beg[q[i].p]=min(beg[q[i].p],i); for (int i=1;i<=cnt;i++)d[i]=INF; d[1]=0;PP aa;aa.x=1;aa.d=d[1];t.push(aa); while(!t.empty()) { PP u=t.top();t.pop(); if (fl[u.x])continue; fl[u.x]=1; if (u.x<=n) { for (int i=beg[u.x];i<=m&&q[i].p==u.x;i++)gengxin(n+1,1,w,1,h,q[i].l,q[i].r,q[i].d,q[i].u,u.d,q[i].t); } else { for (int i=p[u.x-n].lx;i<=p[u.x-n].rx;i++) { if (!g[i].size())continue; int x=ef(i,p[u.x-n].ly); for (int j=x;j<g[i].size()&&(g[i][j].y>=p[u.x-n].ly && g[i][j].y<=p[u.x-n].ry);j++) if (d[u.x]<d[g[i][j].num]) { d[g[i][j].num]=d[u.x];PP aa; aa.x=g[i][j].num;aa.d=d[g[i][j].num]; t.push(aa); } } } } for (int i=2;i<=n;i++)printf("%d ",d[i]); return 0; }