BZOJ4070【APIO2015】雅加达的摩天楼 <分块+最短路>

Problem

【APIO2015】雅加达的摩天楼

Description

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

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

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

Input

输入的第一行包含两个整数和。
接下来行，每行包含两个整数和。

Output

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

Sample Input

Sample Output

Explanation

下面是一种步数为的解决方案：
号跳跃到号摩天楼，再跳跃到号摩天楼（步）。
号将消息传递给号。
号跳跃到号摩天楼,接着跳跃到号摩天楼，再跳跃到号摩天楼（步）。
号将消息传递给号。

HINT

标签：最短路 分块

Solution

分块优化最短路建边。新姿势。

考虑直接建边，由于可以多次跳跃，最多会形成条边，肯定不行。

正解是给每个结点建立若干个辅助结点，像分块一样把建边数降下来。
具体来说，设块大小为，

对于，连出的边数较少，可以直接连边
对于，连出的边数较多，需要对每个点建立个中转节点，第个点的第个中转节点只会通向距离距离恰为的结点的第个中转节点。可以理解为建立的图为层的高架桥，越高层的道路每次走的距离越大。对于点，连接第层的结点（表示结点本身）到第层的结点（表示每次走的距离都是）。

初始化同节点层与层之间的连边，即对于结点，连接其每个中转节点到其本身（即第层的结点）边权为，这样如果在某节点想要停止跳过来时的步长，转用结点本身的步长，则可以从的第个中转节点花费的代价走到结点本身，再花费的代价走到的第个中转节点。

如此，边数和点数都变成了级别，由于卡内存，可以把调成。

Code

#include <bits/stdc++.h>
#define mp make_pair
#define fir top().first
#define sec top().second
#define MAX_N 4000000
#define MAX_M 15000000
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> pii;
typedef priority_queue<pii> pri_que;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, MAGIC, b[MAX_N+5], p[MAX_N+5], d[MAX_N+5], cnt;
struct node {int v, c, nxt;} E[MAX_M+5]; int pr[MAX_N+5]; pri_que que;
void addedge(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
int Dijkstra() {
    int s = b[1], t = b[2];
    memset(d, 0x3f, sizeof d);
    d[s] = 0, que.push(mp(-d[s], s));
    while (!que.empty()) {
        int u = que.sec, w = -que.fir;
        que.pop(); if (d[u]^w) continue;
        for (int i = pr[u], v, c; ~i; i = E[i].nxt)
            if (d[u]+(c=E[i].c) < d[v = E[i].v])
                d[v] = d[u]+c, que.push(mp(-d[v], v));
    }
    return d[t] == INF ? -1 : d[t];
}
int main() {
    memset(pr, -1, sizeof pr);
    read(n), read(m), MAGIC = min((int)sqrt(n), 100);
    for (int i = 1; i <= m; i++) read(b[i]), read(p[i]), b[i]++;
    for (int i = 1; i <= MAGIC; i++)
        for (int j = 1; j <= n; j++) addedge(i*n+j, j, 0);
    for (int i = 1; i <= MAGIC; i++) for (int j = 1; j <= n-i; j++)
        addedge(i*n+j, i*n+i+j, 1), addedge(i*n+i+j, i*n+j, 1);
    for (int i = 1; i <= m; i++)
        if (p[i] <= MAGIC) addedge(b[i], p[i]*n+b[i], 0);
        else {
            for (int j = b[i]+p[i]; j <= n; j += p[i])
                addedge(b[i], j, (j-b[i])/p[i]);
            for (int j = b[i]-p[i]; j >= 1; j -= p[i])
                addedge(b[i], j, (b[i]-j)/p[i]);
        }
    return printf("%d\n", Dijkstra()), 0;
}