LOJ|LOJ 3159: 「NOI2019」弹跳
题目传送门:LOJ #3159。
题意简述:
二维平面上有 \(n\) 个整点,给定每个整点的坐标 \((x_i,y_i)\)。
有 \(m\) 种边,第 \(i\) 种边从 \(p_i\) 号点连向满足 \(l_i\le x_j\le r_i\) 和 \(d_i\le y_j\le u_i\) 的点 \(j\),即一个矩形范围内的所有点。
求 \(1\) 号点到其它每个点的最短路长度。
题解:
考虑 Dijkstra 算法求最短路的过程:
一开始只有起点的距离为 \(0\),而其它点距离为无限大。
每次取出一个距离最短的没被更新过的点,用它更新它能到达的所有未被更新过的点的距离,并将其标记为已被更新。
重复这个过程直到所有点均被更新。
上述过程一般使用单调队列来维护距离最短的点。
而在此题中,一次更新时可能加入的点会有很多很多,不能每次将其一并加入。
可以考虑加入一条边而非点,加入的这条边就代表了这条边连向的所有点的距离。
类似地,每次取出距离最短的边,此时这条边代表的矩形内部的所有点均可以进行更新,因为只会去更新未被更新过的点,所以更新完这些点的距离后,可以把这些点全部删除。
上述方法是最短路中包含“一对多”,“多对多”的边时的处理办法。还有一种方法是使用数据结构模型优化建边,但是一般不会比这种方法来得优。
至于具体如何维护矩形删点操作,删点时可以暴力一个个删除,因为每个点只会被删除一次,问题在于如何快速找到要删除的点。
这里我使用线段树套平衡树(std::set
)维护,外层线段树处理横坐标上的区间,内层平衡树可以快速访问目标点将其删除。
下面是代码,时间复杂度为 \(\mathcal{O}(n\log^2n+m\log m)\):
#include
#include
#include
#include
#include #define mp std::make_pair
typedef std::pair pii;
typedef std::multiset::iterator iter;
const int MN = 70005, MM = 150005;
const int MS = 1 << 18 | 7;
int N, M, W, H, yp[MN], vis[MN], dis[MN];
int h[MN], nxt[MM], et[MM], eL[MM], eR[MM], eD[MM], eU[MM];
std::multiset st[MS];
std::priority_queue pq;
void Ins(int i, int l, int r, int x, int id) {
st[i].insert(mp(yp[id], id));
if (l == r) return ;
int mid = (l + r) >> 1;
if (x <= mid) Ins(i << 1, l, mid, x, id);
else Ins(i << 1 | 1, mid + 1, r, x, id);
}
void Del(int i, int l, int r, int id, int d) {
if (r < eL[id] || eR[id] < l) return ;
if (eL[id] <= l && r <= eR[id]) {
iter it = st[i].lower_bound(mp(eD[id], 0)), tmp;
while (it != st[i].end() && it -> first <= eU[id]) {
int u = it -> second;
if (!vis[u]) {
vis[u] = 1, dis[u] = d;
for (int j = h[u];
j;
j = nxt[j])
pq.push(mp(-d - et[j], j));
}
tmp = it, ++it, st[i].erase(tmp);
}
return ;
}
int mid = (l + r) >> 1;
Del(i << 1, l, mid, id, d);
Del(i << 1 | 1, mid + 1, r, id, d);
}int main() {
freopen("jump.in", "r", stdin);
freopen("jump.out", "w", stdout);
scanf("%d%d%d%d", &N, &M, &W, &H);
for (int i = 1, x;
i <= N;
++i) {
scanf("%d%d", &x, &yp[i]);
Ins(1, 1, W, x, i);
}
for (int i = 1, p;
i <= M;
++i) {
scanf("%d%d%d%d%d%d", &p, &et[i], &eL[i], &eR[i], &eD[i], &eU[i]);
nxt[i] = h[p], h[p] = i;
}
dis[1] = 0, vis[1] = 1;
for (int i = h[1];
i;
i = nxt[i])
pq.push(mp(-et[i], i));
while (!pq.empty()) {
pii ed = pq.top();
pq.pop();
int dis = -ed.first, id = ed.second;
Del(1, 1, W, id, dis);
}
for (int i = 2;
i <= N;
++i) printf("%d\n", dis[i]);
return 0;
}
【LOJ|LOJ 3159: 「NOI2019」弹跳】转载于:https://www.cnblogs.com/PinkRabbit/p/NOI2019D2T1.html
推荐阅读
- 八、「料理风云」
- 「#1-颜龙武」区块链的价值是什么()
- 《深度倾听》第5天──「RIA学习力」便签输出第16期
- 「按键精灵安卓版」关于全分辨率脚本的一些理解(非游戏app)
- 「我的2017」——2017|「我的2017」——2017,大事件盘点
- 「适合发朋友圈的可爱短句文案」
- 「漫威之父」斯坦·李去世,回味老爷子在漫威中客串的各种角色
- 史前艺术的审美类型「清央美术」
- 「未来30年」你的孩子会成为社会精英吗()
- 「日记」他乡,温暖的日子