雅加达的摩天楼
题意描述:
- 有(N)座摩天楼，从左到右依次编号为(0)到(N-1)。
- 有(M)个信息传递员，编号依次为(0)到(M-1)。编号为i的传递员最初在编号为(B_i)的摩天楼，邮递员可以在摩天楼之间跳跃(向前或者向后)，编号为(i)的传递员跳跃能力为(P_i)。
- 当传递员到达一个摩天楼他可以执行两种操作
- 1: 跳跃到其他摩天楼上。
- 2: 将消息传递给当前摩天楼的其他传递员。
- 最终要将编号为(0)的摩天楼信息传递到编号为(1)的摩天楼地方。
输入格式:
- 第一行输入(N)和(M)。((1leq n leq 3*10^4,1leq m leq 3*10^4))
- 接下来第(2)到(M+1)，每行包含两个整数(B_i)和(P_i)。
输出格式:
- 输出一行，表示最小步数，如果无法到达则输出(-1)。
解题思路：
- 分析完题目后可以想到是最短路，对于每一个传递员都可以跳到别处，可以以此建立起点和终点，边权为1。
- 考虑暴力加边的做法，但是如果(p)很小的时候，最坏情况下有(n^2)条边，任何最短路算法都无法通过。
- 优化建图，采用分块的思想: 将(n)点合并为(sqrt{n})个块
- 对于(P_ileqsqrt{n})的传递员：
- 对于某一栋摩天大楼，就把他从一个点转化为一栋真的摩天大楼。
- 对于每栋楼建(sqrt{n})层，每层有(n)个点，第一层代表(p=1)的走法，第二层代表(p=2)的走法,....。其中第(0)代表原先的那个点。
- 然后暴力加边。第(i)层代表(P=i)的情况，间距为(i)的点相互连长度为(1)的边。再把这些辅助点全部连向底边。
- 对于每个(P_i>sqrt{n})的点向其能达到的所有点的第(0)层加边。
- 总边数不会超过(Nsqrt{N})。
- 建图完毕，跑最短路。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = (3e4 + 10)*500;
const int maxm = (3e4 + 10)*500;
int n, m;
int s, t; //起点和终点
int B[maxn], P[maxn]; //起始于B, 跳跃能力为P
int block;
int head[maxn], nex[maxn<<1], ver[maxn<<1], edge[maxn<<1], tot;
inline void add_edge(int x, int y, int z)
{
ver[++tot] = y; edge[tot] = z;
nex[tot] = head[x]; head[x] = tot;
}
inline int get_block(int x, int y){
return x*n + y;
}
int dist[maxn];
bool v[maxn];
void SPFA()
{
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0; queue<int> q;
q.push(s); v[s] = 1;
while(q.size())
{
int x = q.front(); q.pop();
v[x] = 0;
for(int i = head[x]; i; i = nex[i])
{
int y = ver[i], z = edge[i];
if(dist[y] > dist[x] + z)
{
dist[y] = dist[x] + z;
if(!v[y])
{
q.push(y);
v[y] = 1;
}
}
}
}
printf("%d
", dist[t] == 0x3f3f3f3f ? -1 : dist[t]);
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1, x, y; i <= m; i++)
{
scanf("%d%d", &x, &y);
B[i] = x + 1, P[i] = y;
}
//起始位置 终止位置 块的大小
s = B[1], t = B[2]; block = min((int)sqrt(n), 100);
//每一个点转化为一栋楼, 有sqrt(n)层
for(int i = 1; i <= block; i++)
for(int j = 1; j <= n; j++)
{
add_edge(get_block(i, j), j, 0); //楼底到每一层连边
if(j <= n - i) //j条一次跳出范围了
{
//每一层间隔为i的点 跳一次边权为1
add_edge(get_block(i,j), get_block(i,j)+i, 1);
add_edge(get_block(i,j)+i, get_block(i,j), 1);
}
}
for(int i = 1; i <= m; i++) //考虑每一个doge的跳跃能力
{
// 对于每一个传递员, 从楼底到Pi层对应连边
if(P[i] <= block)
add_edge(B[i], get_block(P[i], B[i]), 0);
else
{ //如果大于一个块了 那就暴力加边 因为有sqrt个块 所以加sqrt条边
for(int j = 1; B[i] + j * P[i] <= n; j++)
add_edge(B[i], B[i] + j*P[i], j); //向前跳
for(int j = 1; B[i] - j * P[i] >= 1; j++)
add_edge(B[i], B[i] - j*P[i], j); //向后跳
} //这里最大可能加N*sqrt(N)条边
} SPFA(); //优化后边数有 N*sqrt(N)的规模
return 0;
}