[APIO2015]雅加达的摩天楼

题目描述

印尼首都雅加达市有 NN 座摩天楼,它们排列成一条直线,我们从左到右依次将它们编号为 00 到 N − 1 。除了这 NN 座摩天楼外,雅加达市没有其他摩天楼。 有 MM 只叫做 “doge” 的神秘生物在雅加达市居住,它们的编号依次是 0 到 M − 1 。编号为 i 的 doge 最初居住于编号为 B[i]的摩天楼。每只 doge 都有一种神秘的力量,使它们能够在摩天楼之间跳跃,编号为 i 的 doge 的跳跃能力为 P[i] 在一次跳跃中,位于摩天楼 bb 而跳跃能力为 pp 的 doge 可以跳跃到编号为 b[i]-p[i] 或 b[i] + p[i]的摩天楼。

编号为 0 的 doge 是所有 doge 的首领,它有一条紧急的消息要尽快传送给编号为 1 的 doge。任何一个收到消息的 doge 有以下两个选择:

跳跃到其他摩天楼上;

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

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

输入输出格式

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

输入输出样例

输入样例#1:

5 3 0 2 1 1 4 1 输出样例#1: 5

<——————————————————————–>

SPFA+分块我也是很懵逼

Emm,显然是一个spfa了

但是如果暴力的将每一个doge都与+p,-p暴力连边的话显然是不行的

那么经过深入思考抄题解后,发现可以用分块解决

就是把每一栋楼都分成Unit层

每一层表示的是步长为这个块的doge的跳法

首先先把每一栋楼的每一层都与首层连一条距离为0的边

对于楼上的每层,前后顺次连边,即第i个点的第k层向第i-k点的第k层及i+k点的第k层连边,权值为1

然后读入每个doge的位置和步长

如果一个doge的步长>unit的大小,那么就直接暴力连边

但是如果一个doge的步长<=unit的大小,那么我们就可以将它和他的步长这一层连一条距离为0的边

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
# define p(i,j) i*n+j
const int M = 4000000 ;
const int inf = 100000000 ;
using namespace std;
inline int read(){
    char c=getchar(); int x=0,w=1;
    while(c>'9'||c<'0'){ if(c=='-') w=-1 ;c=getchar() ; }
    while(c>='0'&&c<='9'){ x=x*10+c-'0'; c=getchar() ; }
    return x*w;
}
struct E{
    int nex,to,dis;
}edge[M<<3];
int hea[M],num;
inline void add_edge(int from,int to,int dis){
    edge[++num].nex=hea[from];
    edge[num].to=to;
    edge[num].dis=dis;
    hea[from]=num;
}
int n,m;
int Unit;
int dis[M],s,t;
bool exist[M];
queue<int>q;
inline void Spfa(){
    memset(dis,126/2,sizeof(dis));
    memset(exist,false,sizeof(exist));
    dis[s]=0; q.push(s);
    while(!q.empty()){
        int u=q.front(); q.pop(); exist[u]=false;
        for(int i=hea[u];i;i=edge[i].nex){
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].dis){
                dis[v]=dis[u]+edge[i].dis;
                if(!exist[v]){
                    q.push(v);
                    exist[v]=true;
                }
            }
        }
    }
}
// p ( i,j ) i * n + j 
int main(){
    n=read(); m=read();
    Unit=min(100,(int)sqrt(n));
    for(int i=1;i<=Unit;i++)
      for(int j=1;j<=n;j++)
        add_edge(p(i,j),j,0);
    for(int i=1;i<=Unit;i++)
      for(int j=1;j<=n-i;j++){
      	add_edge(p(i,j),p(i,j+i),1);
      	add_edge(p(i,j+i),p(i,j),1);
      }
    for(int i=1;i<=m;i++){
        int pos=read()+1,jump=read();
        if(i==1) s=pos;
        else if(i==2) t=pos;
        if(jump<=Unit) add_edge(pos,p(jump,pos),0);
        else{
            for(int j=1;pos+j*jump<=n;j++) add_edge(pos,pos+j*jump,j);
            for(int j=1;pos-j*jump>0;j++) add_edge(pos,pos-j*jump,j);
        }
    }
    Spfa();
    if(dis[t]>inf) dis[t]=-1;
    printf("%d\n",dis[t]);
    return 0;
}