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

Problem

【APIO2015】雅加达的摩天楼

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

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

• 跳跃到其他摩天楼上
• 将消息传递给它当前所在的摩天楼上的其他$\mathrm{doge}$

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

Input

输入的第一行包含两个整数$N$和$M$。
接下来$M$行，每行包含两个整数$B_i$和$P_i$。

Output

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

Sample Input

5 3
0 2
1 1
4 1

Sample Output

5

Explanation

下面是一种步数为$5$的解决方案：
$0$号$\mathrm{doge}$跳跃到$2$号摩天楼，再跳跃到$4$号摩天楼（$2$步）。
$0$号$\mathrm{doge}$将消息传递给$2$号$\mathrm{doge}$。
$2$号$\mathrm{doge}$跳跃到$3$号摩天楼,接着跳跃到$2$号摩天楼，再跳跃到$1$号摩天楼（$3$步）。
$2$号$\mathrm{doge}$将消息传递给$1$号$\mathrm{doge}$。

HINT

$1\le N,P_i\le3\times10^4,\;2\le M\le3\times 10^4,\;0\le B_i<N$

标签：最短路 分块

Solution

分块优化最短路建边。新姿势$\mathrm{get}$。

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

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

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

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

如此，边数和点数都变成了$n\sqrt{n}​$级别，由于卡内存，可以把$\mathrm{MAGIC}​$调成$\min(\sqrt{n},100)​$。

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;
}