手机响应式网站开发模板之家,网站黄金比例,城乡建设杂志官方网站,如何本地安装wordpress题意#xff1a;一个whw\times hwh的二维平面上有nnn个城市#xff0c;有mmm个弹跳装置#xff0c;第iii个可以花费tit_iti的时间从城市pip_ipi跳到矩形x∈[l,r],y∈[u,d]x\in [l,r],y\in[u,d]x∈[l,r],y∈[u,d]中的任意一个城市。求从111到其他每个城市的最小时间。 w,…题意一个w×hw\times hw×h的二维平面上有nnn个城市有mmm个弹跳装置第iii个可以花费tit_iti的时间从城市pip_ipi跳到矩形x∈[l,r],y∈[u,d]x\in [l,r],y\in[u,d]x∈[l,r],y∈[u,d]中的任意一个城市。求从111到其他每个城市的最小时间。
w,h≤n≤7×104,m≤1.5×105w,h\leq n\leq7\times 10^4,m\leq1.5\times10^5w,h≤n≤7×104,m≤1.5×105 空间限制128M
考虑直接套dijkstra的思路每次选出dis最小的点松弛它可以到的点然后把它删掉。
挪到二维平面上你需要支持
全局询问最小值矩形取min\minmin删除一个点
用kdt或者二维线段树维护即可。这里用的是二维线段树。
需要注意的细节
要动态开点要用pair记录最小值的编号且初值是(INF,INF)否则可能打了个lazy标记之后first是答案标号却是0。大常数选手需要维护一个最大值剪枝。
#include iostream
#include cstdio
#include cstring
#include cctype
#include vector
#include utility
#define re register
#define MAXN 70005
using namespace std;
const int INF0x7fffffff;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
typedef pairint,int pi;
#define mp make_pair
#define fi first
#define se second
struct tran{int xl,xr,yl,yr;tran(int xl0,int xr0,int yl0,int yr0):xl(xl),xr(xr),yl(yl),yr(yr){}};
inline bool belong(const tran b,const tran a){return a.xlb.xlb.xra.xra.ylb.ylb.yra.yr;}
inline bool ninter(const tran a,const tran b){return (a.xrb.xl||b.xra.xl)||(a.yrb.yl||b.yra.yl);}
struct edge{tran t;int w;};
vectoredge e[MAXN];
#define ch(x) t[p].son[x]
int tot0,rt;
struct node{tran pos;pi mn;int mx,sum,lzy,son[4];}t[MAXN5];
inline int newnode(int xl,int xr,int yl,int yr)
{int ptot;t[p].postran(xl,xr,yl,yr);t[p].mnmp(INF,INF);t[p].mx0;t[p].lzyINF;return p;
}
inline void update(int p)
{t[p].sumt[ch(0)].sumt[ch(1)].sumt[ch(2)].sumt[ch(3)].sum;t[p].mnmp(INF,INF),t[p].mx0;for (re int i0;i4;i) if (ch(i)) t[p].mnmin(t[p].mn,t[ch(i)].mn),t[p].mxmax(t[p].mx,t[ch(i)].mx);
}
inline void pushlzy(int p,int v)
{if (t[p].sum0) return;t[p].mn.fimin(t[p].mn.fi,v),t[p].mxmin(t[p].mx,v),t[p].lzymin(t[p].lzy,v);
}
inline void pushdown(int p)
{if (t[p].lzyINF){for (re int i0;i4;i) pushlzy(ch(i),t[p].lzy);t[p].lzyINF;}
}
void modify(int p,int xl,int xr,int yl,int yr,int x,int y,int v)
{if (!p) pnewnode(xl,xr,yl,yr);if (!belong(tran(x,x,y,y),t[p].pos)) return;pushdown(p);if (t[p].pos.xlt[p].pos.xrt[p].pos.ylt[p].pos.yr) return (void)(t[p].sum(vINF),t[p].mnmp(INF,v),t[p].mx(vINF? 0:INF));int xmid(xlxr)1,ymid(ylyr)1; modify(ch(0),xl,xmid,yl,ymid,x,y,v);modify(ch(1),xl,xmid,ymid1,yr,x,y,v);modify(ch(2),xmid1,xr,yl,ymid,x,y,v);modify(ch(3),xmid1,xr,ymid1,yr,x,y,v); update(p);
}
void modify(int p,tran q,int v)
{if (!p) return;pushdown(p); if (t[p].mxv) return;if (belong(t[p].pos,q)) return pushlzy(p,v);if (ninter(t[p].pos,q)) return;for (int i0;i4;i) modify(ch(i),q,v);update(p);
}
int x[MAXN],y[MAXN],ans[MAXN];
int main()
{int n,m,w,h;nread(),mread(),wread(),hread();for (int i1;in;i){x[i]read(),y[i]read();modify(rt,1,w,1,h,x[i],y[i],i);}for (int i1;im;i){int p,t,l,r,d,u;pread(),tread(),lread(),rread(),dread(),uread();e[p].push_back((edge){tran(l,r,d,u),t});}modify(1,tran(x[1],x[1],y[1],y[1]),0);for (int T1;Tn;T){pi tmpt[1].mn;int utmp.se,distmp.fi;ans[u]dis;for (int i0;i(int)e[u].size();i)modify(1,e[u][i].t,dise[u][i].w);modify(rt,1,w,1,h,x[u],y[u],INF);}for (int i2;in;i) printf(%d\n,ans[i]);return 0;
}
