本题卡空间。
线段树优化建图。但是我们不能显式建图甚至是显式建出二维线段树不然会 MLE。
于是我们使用线段树套 set 来做这个题，第一位用线段树第二位用 set 直接查。
然后注意到点权图最短路第一次松弛即为最优，于是我们把矩形建出虚点然后 dijkstra，复杂度做到了 \(\mathrm{O}(n \log^2 n)\)（\(n, m\) 视为同阶）。
然后卡卡空间就过了。
#include <bits/stdc++.h>
#define llong long long
#define N 250005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}#define x1 test1
#define y1 test2int n, m, w, h;
int x[N], y[N];
int x1[N], y1[N], x2[N], y2[N]; int c[N];
vector<int> op[N];typedef pair<int, int> Node;
set<Node> val[N<<2];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)inline void modify(int posx, int posy, int id, int x = 1, int l = 1, int r = n){val[x].emplace(posy, id);if(l == r) return;if(posx <= mid) modify(posx, posy, id, ls(x), l, mid );else modify(posx, posy, id, rs(x), mid+1, r);return;
}int vis[N], dis[N];
priority_queue<Node, vector<Node>, greater<Node> > pq;
inline void operate(int u, int x = 1, int l = 1, int r = n){if(x1[u] <= l && x2[u] >= r){auto it = val[x].lower_bound({y1[u], 0});while(it != val[x].end() && it->first <= y2[u]){int v = it->second;if(vis[v]) goto del;if(dis[v] > dis[u+n]){dis[v] = dis[u+n];vis[v] = true;pq.emplace(dis[v], v);}del:;auto tmp = it++;val[x].erase(tmp);}return;}if(x1[u] <= mid) operate(u, ls(x), l, mid );if(x2[u] > mid) operate(u, rs(x), mid+1, r);return;
}
inline void dijkstra(){for(int i = 1; i <= n+m; ++i)dis[i] = 1e9+7;dis[1] = 0, vis[1] = true;pq.emplace(0, 1);while(pq.size()){int u = pq.top().second; pq.pop();if(u <= n){for(int v : op[u]){dis[v+n] = dis[u]+c[v], vis[v+n] = true;pq.emplace(dis[v+n], v+n);}}else operate(u-n);}
}int main(){// freopen("in.txt", "r", stdin);read(n, m, w, h);for(int i = 1; i <= n; ++i)read(x[i], y[i]), modify(x[i], y[i], i);for(int i = 1, x; i <= m; ++i){read(x, c[i], x1[i], x2[i], y1[i], y2[i]);op[x].push_back(i);}dijkstra();for(int i = 2; i <= n; ++i)printf("%d\n", dis[i]);return 0;
}