这玩意在 uoj 老哥的毒瘤数据上 MLE 了……

思路就是普通的 kdt 优化建图+隐式建图+铃的剪枝

死活看不出来哪里可以 MLE

#include<algorithm>
#include<queue>
#include<cctype>
#include<cstdio>
using namespace std;
inline int readint(){
	int x=0;
	bool f=0;
	char c=getchar();
	while(!isdigit(c)&&c!='-') c=getchar();
	if(c=='-'){
		f=1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return f?-x:x;
}
const int maxn=7e4+5,maxm=1.5e5+5;
int n,m,x[maxn],y[maxn],t[maxm],L[maxm],R[maxm],D[maxm],U[maxm];
vector<int> p[maxn];
int rt,ch[maxn][2],mnx[maxn],mny[maxn],mxx[maxn],mxy[maxn],ord[maxn];
bool cmp1(int a,int b){
	return x[a]<x[b];
}
bool cmp2(int a,int b){
	return y[a]<y[b];
}
void pushup(int o){
	mnx[o]=mxx[o]=x[o];
	mny[o]=mxy[o]=y[o];
	if(ch[o][0]){
		mnx[o]=min(mnx[o],mnx[ch[o][0]]);
		mxx[o]=max(mxx[o],mxx[ch[o][0]]);
		mny[o]=min(mny[o],mny[ch[o][0]]);
		mxy[o]=max(mxy[o],mxy[ch[o][0]]);
	}
	if(ch[o][1]){
		mnx[o]=min(mnx[o],mnx[ch[o][1]]);
		mxx[o]=max(mxx[o],mxx[ch[o][1]]);
		mny[o]=min(mny[o],mny[ch[o][1]]);
		mxy[o]=max(mxy[o],mxy[ch[o][1]]);
	}
}
int build(int l,int r,bool d){
	if(l==r){
		pushup(ord[r]);
		return ord[r];
	}
	if(l+1==r){
		ch[ord[l]][1]=ord[r];
		pushup(ord[r]);
		pushup(ord[l]);
		return ord[l];
	}
	int mid=l+(r-l)/2;
	nth_element(ord+l,ord+mid,ord+r+1,d?cmp1:cmp2);
	ch[ord[mid]][0]=build(l,mid-1,!d);
	ch[ord[mid]][1]=build(mid+1,r,!d);
	pushup(ord[mid]);
	return ord[mid];
}
int dis[maxn*2];
void query(int o,int l,int r,int d,int u,vector<int>& res,int now){
	if(dis[o+n]<=now) return;
	if(l<=mnx[o]&&r>=mxx[o]&&d<=mny[o]&&u>=mxy[o]){
		res.push_back(o+n);
		return;
	}
	if(l<=x[o]&&r>=x[o]&&d<=y[o]&&u>=y[o]) res.push_back(o);
	int lc=ch[o][0],rc=ch[o][1];
	if(lc&&l<=mxx[lc]&&r>=mnx[lc]&&d<=mxy[lc]&&u>=mny[lc])
		query(lc,l,r,d,u,res,now);
	if(rc&&l<=mxx[rc]&&r>=mnx[rc]&&d<=mxy[rc]&&u>=mny[rc])
		query(rc,l,r,d,u,res,now);
}
bool vis[maxn*2];
typedef pair<int,int> pii;
const int inf=2e9;
void dijkstra(){
	for(int i=1;i<=n*2;i++) dis[i]=inf;
	priority_queue<pii,vector<pii>,greater<pii> > pq;
	dis[1]=0;
	pq.push(pii(0,1));
	while(!pq.empty()){
		int u=pq.top().second;
		pq.pop();
		if(vis[u]) continue;
		vis[u]=1;
		if(u<=n) for(int i=0;i<(int)p[u].size();i++){
			int v=p[u][i];
			vector<int> res;
			if(L[v]<=mxx[rt]&&R[v]>=mnx[rt]&&D[v]<=mxy[rt]&&U[v]>=mny[rt])
				query(rt,L[v],R[v],D[v],U[v],res,dis[u]+t[v]);
			for(int j=0;j<(int)res.size();j++) if(dis[res[j]]>dis[u]+t[v]){
				dis[res[j]]=dis[u]+t[v];
				pq.push(pii(dis[res[j]],res[j]));
			}
		}
		else{
			if(ch[u-n][0]&&dis[ch[u-n][0]+n]>dis[u]){
				dis[ch[u-n][0]+n]=dis[u];
				pq.push(pii(dis[ch[u-n][0]+n],ch[u-n][0]+n));
			}
			if(ch[u-n][1]&&dis[ch[u-n][1]+n]>dis[u]){
				dis[ch[u-n][1]+n]=dis[u];
				pq.push(pii(dis[ch[u-n][1]+n],ch[u-n][1]+n));
			}
			if(dis[u-n]>dis[u]){
				dis[u-n]=dis[u];
				pq.push(pii(dis[u-n],u-n));
			}
		}
	}
}
int main(){
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	n=readint();
	m=readint();
	readint();
	readint();
	for(int i=1;i<=n;i++){
		x[i]=readint();
		y[i]=readint();
	}
	for(int i=0;i<m;i++){
		p[readint()].push_back(i);
		t[i]=readint();
		L[i]=readint();
		R[i]=readint();
		D[i]=readint();
		U[i]=readint();
	}
	for(int i=1;i<=n;i++) ord[i]=i;
	rt=build(1,n,0);
	dijkstra();
	for(int i=2;i<=n;i++) printf("%d\n",dis[i]);
	return 0;
}
``