P3645 [APIO2015] 雅加达的摩天楼
题目描述
印尼首都雅加达市有NNN座摩天楼，它们排列成一条直线，我们从左到右依次将它们编号为000到N−1N − 1N−1。除了这NNN座摩天楼外，雅加达市没有其他摩天楼。
有MMM只叫做 “doge” 的神秘生物在雅加达市居住，它们的编号依次是000到M−1M − 1M−1。编号为iii的 doge 最初居住于编号为BiB_iBi的摩天楼。每只 doge 都有一种神秘的力量，使它们能够在摩天楼之间跳跃，编号为iii的 doge 的跳跃能力为PiP_iPi（Pi>0P_i > 0Pi>0）。
在一次跳跃中，位于摩天楼bbb而跳跃能力为ppp的 doge 可以跳跃到编号为b−pb - pb−p（如果0≤b−p<N0 \leq b - p < N0≤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−1−1。
输入输出样例 #1
输入 #1
5 3 0 2 1 1 4 1输出 #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
C++实现
#include<bits/stdc++.h>usingnamespacestd;constintN=30000+5;bitset<N>vis[N];vector<int>p[N];structnode{intpos,jump,dep;node(){}node(int_p,int_j,int_d){pos=_p;jump=_j;dep=_d;}};deque<node>q;intn,B[N],P[N];voidbfs(){node u;while(!q.empty()){u=q.front();q.pop_front();//cout<<u.pos<<" "<<u.jump<<endl;if(u.pos==B[1])cout<<u.dep,exit(0);if(vis[u.pos][u.jump])continue;vis[u.pos][u.jump]=1;for(inti=0;i<p[u.pos].size();++i)q.push_front(node(u.pos,p[u.pos][i],u.dep));if(u.pos-u.jump>=0)q.push_back(node(u.pos-u.jump,u.jump,u.dep+1));if(u.pos+u.jump<n)q.push_back(node(u.pos+u.jump,u.jump,u.dep+1));}cout<<-1;}intmain(){intm;cin>>n>>m;for(inti=0;i<m;++i){cin>>B[i]>>P[i];p[B[i]].push_back(P[i]);}q.push_back(node(B[0],P[0],0));bfs();return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
