题目地址：洛谷：【P3645】[APIO2015]雅加达的摩天楼 – 洛谷、BZOJ：Problem 4070. — [Apio2015]雅加达的摩天楼

题目描述

印尼首都雅加达市有 N 座摩天楼，它们排列成一条直线，我们从左到右依次将它们编号为 0 到 N−1。除了这 N 座摩天楼外，雅加达市没有其他摩天楼。
有 M 只叫做 “doge” 的神秘生物在雅加达市居住，它们的编号依次是 0 到 M−1。编号为 i 的 doge 最初居住于编号为 Bi 的摩天楼。每只 doge 都有一种神秘的力量，使它们能够在摩天楼之间跳跃，编号为 i 的 doge 的跳跃能力为 Pi （Pi>0）。
在一次跳跃中，位于摩天楼 b 而跳跃能力为 p 的 doge 可以跳跃到编号为 b−p （如果 0≤b−p<N）或 b+p （如果 0≤b+p<N）的摩天楼。
编号为 0 的 doge 是所有 doge 的首领，它有一条紧急的消息要尽快传送给编 号为 1 的 doge。任何一个收到消息的 doge 有以下两个选择:

• 跳跃到其他摩天楼上；
• 将消息传递给它当前所在的摩天楼上的其他 doge。

请帮助 doge 们计算将消息从 0 号 doge 传递到 1 号 doge 所需要的最少总跳跃步数，或者告诉它们消息永远不可能传递到 1 号 doge。

输入输出格式

输入格式：
输入的第一行包含两个整数 N 和 M。
接下来 M 行，每行包含两个整数 Bi 和 Pi。

输出格式：
输出一行，表示所需要的最少步数。如果消息永远无法传递到 1 号 doge，输出 −1。

输入输出样例

输入样例#1：

5 3
0 2
1 1
4 1

输出样例#1：

5

说明

所有数据都保证 0≤Bi<N。
子任务 1 （10 分），1≤N≤10，1≤Pi≤10，2≤M≤3
子任务 2 （12 分），1≤N≤100，1≤Pi≤100，2≤M≤2000
子任务 3 （14 分），1≤N≤2000，1≤Pi≤2000，2≤M≤2000
子任务 4 （21 分），1≤N≤2000，1≤Pi≤2000，2≤M≤30000
子任务 5 （43 分），1≤N≤30000，1≤Pi≤30000，2≤M≤30000

题解

其实可以把这个转化成一个最短路问题，从一个有doge的建筑向它能够到的所有建筑连有向边，但是如果p太小，边的数量甚至可以达到n^2。
我们考虑将p在\min(\sqrt{n}, 100)以内的点进行一个预处理，即按照枚举这些p，对于每个建筑每个p值建新点，把所有可能的边都直接建起来，并使拆出来的这些点都有出边指向这些点所在的建筑原来的点。进行了这一通预处理，对于p在上述范围内的点，只需要从它所在的建筑原点建出边指向对应的p拆出来的点即可。优化后的边数就只有n \sqrt{n}规模了。
由于vector占用空间过大，推荐使用邻接表存图。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>

#include <algorithm>
#include <vector>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 30005;

int n, m;

struct Edge {
    int to, w, nxt;
} gra[MAXN * 500];
int head[MAXN * 200], tot;

inline void addedge(int u, int v, int w) {
    gra[tot] = Edge {v, w, head[u]}; head[u] = tot++;
}

int dis[MAXN * 200];
bool inque[MAXN * 200];
std::queue<int> que;

inline void spfa(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; inque[s] = true; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(dis[v] > dis[u] + gra[i].w) {
                dis[v] = dis[u] + gra[i].w;
                if(!inque[v]) {
                    inque[v] = true; que.push(v);
                }
            }
        }
    }
}

int b[MAXN], p[MAXN];

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint();
    for(int i = 1; i <= m; i++) {
        b[i] = readint() + 1; p[i] = readint();
    }
    int sqn = std::min(int(sqrt(n)), 100);
    for(int i = 1; i <= sqn; i++) {
        for(int j = 1; j <= n; j++) {
            addedge(i * n + j, j, 0);
            if(j + i <= n) {
                addedge(i * n + j, i * n + j + i, 1);
                addedge(i * n + j + i, i * n + j, 1);
            }
        }
    }
    for(int i = 1; i <= m; i++) {
        if(p[i] <= sqn) {
            addedge(b[i], b[i] + p[i] * n, 0);
        } else {
            for(int j = 1; b[i] + p[i] * j <= n; j++) {
                addedge(b[i], b[i] + p[i] * j, j);
            }
            for(int j = 1; b[i] - p[i] * j >= 1; j++) {
                addedge(b[i], b[i] - p[i] * j, j);
            }
        }
    }
    spfa(b[1]);
    printf("%d", dis[b[2]] == 0x3f3f3f3f ? -1 : dis[b[2]]);
    return 0;
}