Rockdu's Blog

印尼首都雅加达市有 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 有以下两个选择:

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

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

输入格式

输入的第一行包含两个整数 N 和 M。

接下来 M 行，每行包含两个整数 Bi 和 Pi。

输出格式

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

样例一

input

5 3
0 2
1 1
4 1

output

5

explanation

下面是一种步数为 5 的解决方案：

• 0 号 doge 跳跃到 2 号摩天楼，再跳跃到 4 号摩天楼（2 步）。
• 0 号 doge 将消息传递给 2 号 doge。
• 2 号 doge 跳跃到 3 号摩天楼,接着跳跃到 2 号摩天楼，再跳跃到 1 号摩天楼（3 步）。
• 2 号 doge 将消息传递给 1 号 doge。

子任务

所有数据都保证 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

时间限制：1s1s

空间限制：256MB

这道题的思想还是很值得借鉴的。

首先我们不难构出一个n^2级别的图，把每个摩天楼的状态拆成N种可能的跳跃步数，这样就能拿下40~50分的样子（突然感叹往年APIO真的良心）。

然后我们考虑一下优化构图，我们把跳跃步数分两种来构：sqrt(n)以下、sqrt(n)以上。

对于第一种，我们每个摩天楼下开sqrt(n)个辅助点，第i个点表示到当前摩天楼可以步长为i的状态，把它们和主点都连长度为0的单向边，如果一个摩天大楼里住着跳跃步长为i的doge，那么主点项第i个点连长度为0的单向边。

然后我们把每个摩天楼的第i个辅助点，连向左右两边跳i格到达的摩天楼的第i个辅助点。这样总的边数是O(n * sqrt(n))的。

对于第二种，我们直接在主点间连就好了，因为一个主点跳出去最多也就sqrt(n)条边，同样的，边数为(n * sqrt(n))

这样一遍SPFA就过了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
const int maxn = 4e4 + 5;
const int sqt = 100, inf = 0x3f3f3f3f;
int node[maxn][sqt + 50], cnt;
int n, m, u, v;
vector<int > doge[maxn], Ld[maxn];

struct STU {int x, p;} S, T;

int dis[maxn * (sqt + 50)], vis[maxn * (sqt + 50)];

#define Gid(u) ((u.p <= sqt) ? node[u.x][u.p] : node[u.x][0])

void rel(queue<STU > & q, STU u, STU v, int w) {
    int ui = Gid(u), vi = Gid(v);
    if(dis[ui] + w < dis[vi]) {
        dis[vi] = dis[ui] + w;
        if(!vis[vi]) q.push(v), vis[vi] = 1;
    }
}

inline bool ilg(STU u) {
    return u.x < 0 || u.x > n - 1;
}

void SPFA(STU s, STU t) {
    memset(dis, 0x3f, sizeof(dis));
    queue<STU > q;
    q.push(s), dis[Gid(s)] = 0;
    STU u, v; int len;
    while(!q.empty()) {
        u = q.front();
        //cerr << u.x << " " << u.p << endl;
        q.pop(), vis[Gid(u)] = 0;
        if(u.p) {
            if(!ilg(v = (STU){u.x - u.p, u.p})) rel(q, u, v, 1);
            if(!ilg(v = (STU){u.x + u.p, u.p})) rel(q, u, v, 1);
            rel(q, u, (STU){u.x, 0}, 0);
        } else {
        	rel(q, u, (STU){u.x, 0}, 0);
            for(register int i = doge[u.x].size() - 1; i >= 0; --i)
                v = (STU){u.x, doge[u.x][i]}, rel(q, u, v, 0);
            for(register int i = Ld[u.x].size() - 1; i >= 0; --i) {
                len = Ld[u.x][i];
                for(register int stp = 1; u.x + stp * len < n; ++stp)
                    v = (STU){u.x + len * stp, 0}, rel(q, u, v, stp);
                for(register int stp = 1; u.x - stp * len >= 0; ++stp)
                    v = (STU){u.x - len * stp, 0}, rel(q, u, v, stp);
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(register int i = 0; i < n; ++i)
        for(register int j = 0; j <= sqt; ++j)
            node[i][j] = ++cnt;
    scanf("%d%d", &u, &v), S = (STU){u, v};
    if(v <= sqt) doge[u].push_back(v); else Ld[u].push_back(v);
    scanf("%d%d", &u, &v), T = (STU){u, v};
    if(v <= sqt) doge[u].push_back(v); else Ld[u].push_back(v);
    for(register int i = 1; i <= m - 2; ++i) {
        scanf("%d%d", &u, &v), doge[u].push_back(v);
        if(v <= sqt) doge[u].push_back(v); else Ld[u].push_back(v);
    }
    SPFA((STU){S.x, 0}, T);
    int ans = inf;
    for(register int i = 0; i <= sqt; ++i)
    	ans = min(ans, dis[node[T.x][i]]);
    printf("%d", ans != inf ? ans : -1);
    return 0;
}