打卡信奥刷题（2749）用C++实现信奥题 P3645 [APIO2015] 雅加达的摩天楼-深圳市維司達科技有限公司

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

说明/提示

【样例解释】

下面是一种步数为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;}