题目描述
印尼首都雅加达市有 NNN 座摩天楼,它们排列成一条直线,我们从左到右依次将它们编号为 000 到 $N − 1$ 。除了这 NNN 座摩天楼外,雅加达市没有其他摩天楼。
有 MMM 只叫做 “doge” 的神秘生物在雅加达市居住,它们的编号依次是 000 到 $M − 1$ 。编号为 iii 的 doge 最初居住于编号为 BiB_iBi 的摩天楼。每只 doge 都有一种神秘的力量,使它们能够在摩天楼之间跳跃,编号为 iii 的 doge 的跳跃能力为 PiP_iPi ( Pi>0P_i > 0Pi>0 )。
在一次跳跃中,位于摩天楼 bbb 而跳跃能力为 ppp 的 doge 可以跳跃到编号为 $b − p$ (如果 $0 \leq b − p < N$ )或 b+pb + pb+p (如果 0≤b+p<N0 \leq b + p < N0≤b+p<N )的摩天楼。
编号为 000 的 doge 是所有 doge 的首领,它有一条紧急的消息要尽快传送给编
号为 111 的 doge。任何一个收到消息的 doge 有以下两个选择:
跳跃到其他摩天楼上;
将消息传递给它当前所在的摩天楼上的其他 doge。
请帮助 doge 们计算将消息从 000 号 doge 传递到 111 号 doge 所需要的最少总跳跃步数,或者告诉它们消息永远不可能传递到 111 号 doge。
输入输出格式
输入格式:输入的第一行包含两个整数 NNN 和 MMM 。
接下来 MMM 行,每行包含两个整数 BiB_iBi 和 PiP_iPi 。
输出格式:输出一行,表示所需要的最少步数。如果消息永远无法传递到 111 号 doge,输出 $−1$ 。
输入输出样例
5 30 21 14 1
5
说明
【样例解释】
下面是一种步数为 555 的解决方案:
000 号 doge 跳跃到 222 号摩天楼,再跳跃到 444 号摩天楼( 222 步)。
000 号 doge 将消息传递给 222 号 doge。
222 号 doge 跳跃到 333 号摩天楼,接着跳跃到 222 号摩天楼,再跳跃到 111 号摩天楼( 333 步)。
222 号 doge 将消息传递给 111 号 doge。
【数据范围】
所有数据都保证 $0≤Bi<N0 \leq B_i < N0≤Bi<N $。
子任务 1 (10 分) $1≤N≤101 \leq N \leq 101≤N≤10$
$1≤Pi≤101 \leq P_i \leq 101≤Pi≤10$
$2≤M≤32 \leq M \leq 32≤M≤3$
子任务 2 (12 分)$1≤N≤1001 \leq N \leq 1001≤N≤100$
$1≤Pi≤1001 \leq P_i \leq 1001≤Pi≤100$
$2≤M≤20002 \leq M \leq 20002≤M≤2000$
子任务 3 (14 分) $1≤N≤20001 \leq N \leq 20001≤N≤2000$
$1≤Pi≤20001 \leq P i ≤ 20001≤Pi≤2000$
$2≤M≤20002 \leq M \leq 20002≤M≤2000$
子任务 4 (21 分) $1≤N≤20001 \leq N \leq 20001≤N≤2000$
$1≤Pi≤20001 \leq P_i \leq 20001≤Pi≤2000$
$2≤M≤300002 \leq M \leq 300002≤M≤30000$
子任务 5 (43 分) $1≤N≤300001 \leq N \leq 300001≤N≤30000$
$1≤Pi≤300001 \leq P_i \leq 300001≤Pi≤30000$
$2≤M≤300002 \leq M \leq 300002≤M≤30000$
首先对于一个(i,p),如果暴力建边,复杂度$O(mn)$
首先考虑分块
如果p大于$n^{\frac{1}{2}}$那么直接建边$O(n^{\frac{1}{2}})$
如果p小于$n^{\frac{1}{2}}$
首先有一个思路就是设vis[i][p]表示是否考虑过(i,p)
这样就不会重复建边,边数最多$m*n^{\frac{1}{2}}*log$
这样简单易懂,但空间却不够
如果不是捆绑测试就能拿很多分
于是转化建边思路,在p小于$n^{\frac{1}{2}}$
每个点建$n^{\frac{1}{2}}$个辅助点,设为<i,p>点
事先这样建边
1.给每个<i,p>向$i$连边,权为0
2.给每个<i,p>与<i+p,p>建双向边
如果有一个doge是(i,p)的,那么
$i$连<i,p>,边权为0
这样建边保证跑最短路时从i跳到i+p,可以直接从辅助点
而且保证了一个路径必然是从有doge的地方出发的,不然根本到不了相应的辅助点
这样边数保证在$m*n^{\frac{1}{2}}$
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 struct Node 9 {10 int next,to,dis;11 }edge[30001*101*5];12 int dist[30001*101],lim,S,T,inf,head[30001*101],n,m,num,cnt;13 bool vis[30001][101];14 queue Q;15 bool viss[30001*101];16 int get_id(int x,int y)17 {18 return y*n+x;19 }20 void add(int u,int v,int dis)21 {22 num++;23 edge[num].next=head[u];24 head[u]=num;25 edge[num].to=v;26 edge[num].dis=dis;27 }28 void SPFA()29 { int i;30 memset(dist,127/3,sizeof(dist));31 Q.push(S);32 inf=dist[0];33 memset(viss,0,sizeof(viss));34 dist[S]=0;35 while (Q.empty()==0)36 {37 int u=Q.front();38 Q.pop();39 viss[u]=0;40 for (i=head[u];i;i=edge[i].next)41 {42 int v=edge[i].to;43 if (dist[v]>dist[u]+edge[i].dis)44 {45 dist[v]=dist[u]+edge[i].dis;46 if (viss[v]==0)47 {48 viss[v]=1;49 Q.push(v);50 }51 }52 }53 }54 }55 int main()56 { int i,b,p,j;57 cin>>n>>m;58 lim=min((int)sqrt(n),100);59 for (i=1;i<=n;i++)60 for (j=1;j<=lim;j++)61 add(get_id(i,j),i,0);62 for (i=1;i<=n;i++)63 for (j=1;j<=lim;j++)64 if (i+j<=n)65 add(get_id(i,j),get_id(i+j,j),1),add(get_id(i+j,j),get_id(i,j),1);66 for (i=0;i lim)73 {cnt=0;74 for (j=b;j+p<=n;j+=p)75 {76 add(b,j+p,++cnt);77 }78 cnt=0;79 for (j=b;j-p>0;j-=p)80 {81 add(b,j-p,++cnt);82 }83 }84 else85 {86 add(b,get_id(b,p),0);87 }88 }89 SPFA();90 if (dist[T]==inf) cout<<-1;91 else 92 cout<