题解 P1442 【铁球落地】
CodyTheWolf · · 题解
看到各位都是拿线段树优化DP写的，其实这题跑最短路会更容易理解，代码也好打。
最主要是代码跑的飞快ww，是目前的rank1
全部节点：Accepted 100 用时: 136ms / 内存: 8304KB
大致思路：
1.对木板按照高度排序
2.对于每一个木板，暴力枚举更低的木板，如果可以承接掉下的小球，使当前木板的左或右端点和可到达的木板的左右端点相连，路的权值可以用坐标计算得到。注意：用DFS或者BFS跟着小球能下落的木板枚举，而不是全部都枚举，因为有些木板小球根本落不下。还要记得打标记防止一个木板被重复搜索。如果当前木板有端点没有承接的木板，判断其会不会掉到地板上并连边。
小技巧：小球用0表示，左端点用1-n表示，右端点用(n+1)-2n表示，地板用2n+1表示
3.随便跑个最短路径得到答案（到2n+1的最小值）即可。
代码如下：部分操作有注释
#pragma warning (disable:4996)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <deque>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 5, maxm = 4e5 + 5, inf = 0x7fffffff;
int head[maxm], nxt[maxm], v[maxm], w[maxm], h[maxn], x[maxn], y[maxn], dis[maxn];//h为高度，xy为左右端点
bool vis[maxn];
int n, m, cnt, sx, sy;
inline void addline(int x, int y, int z) { v[cnt] = y, w[cnt] = z, nxt[cnt] = head[x], head[x] = cnt++; }
inline int read()
{
register int x = 0;
register char c = getchar();
while (c<'0' || c>'9') c = getchar();
while (c >= '0'&&c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x;
}
inline void qsort(int l, int r)//手写快排
{
register int mid = h[(l + r) >> 1], L = l, R = r;
while (l <= r)
{
while (h[l] > mid) l++;
while (h[r] < mid) r--;
if (l <= r) { swap(h[l], h[r]), swap(x[l], x[r]), swap(y[l], y[r]), l++, r--; }
}
if (L < r) qsort(L, r);
if (l < R) qsort(l, R);
return;
}
inline void connect()//重点操作：连边
{
//0号为铁球，一倍点（1-n）为左端点，二倍点（n+1-2n)为右端点，2*n+1为地板（最终汇点）
addline(0, 1, sy - h[1] + sx - x[1]), addline(0, n + 1, sy - h[1] + y[1] - sx);
//应该是数据原因导致排序后第一块木板一定在铁球下方，所以让其和木板的左右两端点相连，假如改数据也没问题，在读入时把大于小球高度的木板全部删除，再在这个函数中按高度枚举到能接到小球的木板当成1号木板即可
queue<int> Q;//用队列辅助链接
while (!Q.empty()) Q.pop();
Q.push(1);//第一块木板入队
while (!Q.empty())
{
int i = Q.front(); Q.pop();
bool left = false, right = false;//小剪枝：左右都有木板承接就可以不用枚举了
for (int j = i + 1; h[i] > h[j] && h[i] - h[j] <= m && j <= n; j++)//暴力枚举能落下的木板
{
if (!left && x[j] < x[i] && x[i] < y[j])//计算木板i的左端点是否能落到木板j，根据不等式推一下就明白了
{
//如果可以
addline(i, j, h[i] - h[j] + x[i] - x[j]);//木板i的左端点链接木板j的左端点
addline(i, j + n, h[i] - h[j] + y[j] - x[i]);//木板i的左端点链接木板j的右端点（二倍点）
left = true;
if (!vis[j]) Q.push(j), vis[j] = true;//j没入队过才能搜，防止搜多超时
}
if (!right && x[j] < y[i] && y[i] < y[j])//计算木板i的右端点是否能落到木板j，与上面同理
{
addline(i + n, j, h[i] - h[j] + y[i] - x[j]);
addline(i + n, j + n, h[i] - h[j] + y[j] - y[i]);
right = true;
if (!vis[j]) Q.push(j), vis[j] = true;
}
if (left && right) break;//左右端点都有木板接着就不用枚举了
}
if (!left&&h[i] <= m) addline(i, n << 1 | 1, h[i]);//如果左端点没有落点，判断能不能落到地上(点为2*n+1)
if (!right&&h[i] <= m) addline(i + n, n << 1 | 1, h[i]);//判断右端点，同理
}
return;
}
inline void SPFA()//SPFA+SLF优化
{
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
deque<int> Q;
while (!Q.empty()) Q.pop_back();
dis[0] = 0, Q.push_back(0), vis[0] = true;
while (!Q.empty())
{
int x = Q.front(); Q.pop_front(); vis[x] = false;
for (register int i = head[x]; i != -1; i = nxt[i])
if (dis[v[i]] > dis[x] + w[i])
{
dis[v[i]] = dis[x] + w[i];
if (!vis[v[i]])
{
vis[v[i]] = true;
if (!Q.empty())
{
if (dis[v[i]] > dis[Q.front()]) Q.push_back(v[i]);
else Q.push_front(v[i]);
}
else Q.push_back(v[i]);
}
}
}
return;
}
int main()
{
memset(head, -1, sizeof(head));
n = read(), m = read(), sx = read(), sy = read();//sx,sy为小球坐标
for (int i = 1; i <= n; i++) h[i] = read(), x[i] = read(), y[i] = read();
qsort(1, n), connect(), SPFA();//先排序，连接好边就跑一边SPFA
printf("%d\n", dis[n << 1 | 1]);//最终汇点，即地板（2*n+1）离小球的最短距离即是答案
return 0;
}小吐槽：
一开始连边没有打标记，以为是最短路超时了，上了各种优化（SPFA+SLF，快读，手写快排等等），所以导致代码很长还调了很久QwQ