【BZOJ4070】雅加达的摩天楼（APIO2015）-分块+最短路

做法：本题需要用到分块+最短路。
看到这题，第一个想法就是，从每只狗所在的点mn条边，时间和空间上都不能承受。
还有一种想法，就是用类似于网络流的思想，先把每个点拆成n2的，不能承受。
观察数据范围，容易想到用分块的思想分类讨论，从而把这两种暴力中和成一种更优的做法。在第一种做法中，一只跳跃能力为)条边了，于是就可以用SPFA做了。
最后要注意的是，块的大小不能太大，否则会MLE，100是合适的。
以下是本人代码（洛谷AC，BZOJ上T了，有待解决）：

#include <bits/stdc++.h>
using namespace std;
const int N=30000;
const int inf=1000000000;
int n,m,S,T,blocksiz;
int first[N*200+10]={0},tot=0,dis[N*200+10];
bool vis[N*200+10]={0};
struct edge
{
    int v,next,d;
}e[N*500];
queue<int> Q;

int point(int x,int y)
{
    return x*(blocksiz+1)+y+1;
}

void insert(int a,int b,int d)
{
    e[++tot].v=b;
    e[tot].next=first[a];
    e[tot].d=d;
    first[a]=tot;
}

void init()
{
    scanf("%d%d",&n,&m);
    blocksiz=min((int)(sqrt(n)+1),100);
    for(int i=0;i<m;i++)
    {
        int b,p;
        scanf("%d%d",&b,&p);
        if (i==0) S=point(b,0);
        if (i==1) T=point(b,0);
        if (p>blocksiz)
        {
            for(int j=1;b+j*p<n;j++)
                insert(point(b,0),point(b+j*p,0),j);
            for(int j=1;b-j*p>=0;j++)
                insert(point(b,0),point(b-j*p,0),j);
        }
        else insert(point(b,0),point(b,p),0);
    }

    for(int i=1;i<=blocksiz;i++)
    {
        for(int j=0;j<n;j++)
            insert(point(j,i),point(j,0),0);
        for(int j=0;j<i;j++)
        {
            for(int k=1;j+k*i<n;k++)
            {
                insert(point(j+(k-1)*i,i),point(j+k*i,i),1);
                insert(point(j+k*i,i),point(j+(k-1)*i,i),1);
            }
        }
    }
}

void spfa()
{
    for(int i=1;i<=(blocksiz+1)*n;i++)
        dis[i]=inf;
    dis[S]=0;
    Q.push(S);
    vis[S]=1;
    while(!Q.empty())
    {
        int v=Q.front();Q.pop();
        for(int i=first[v];i;i=e[i].next)
            if (dis[v]+e[i].d<dis[e[i].v])
            {
                dis[e[i].v]=dis[v]+e[i].d;
                if (!vis[e[i].v])
                {
                    Q.push(e[i].v);
                    vis[e[i].v]=1;
                }
            }
        vis[v]=0;
    }

    if (dis[T]==inf) printf("-1");
    else printf("%d
",dis[T]);
}

int main()
{
    init();
    spfa();

    return 0;
}