#include<bits/stdc++.h>
using namespace std ;
const int maxn = 3e4+123 ;
priority_queue <tuple<int,int,int> , vector <tuple<int,int,int>> , greater<tuple<int,int,int>> >bfs ;
vector <int> doge[maxn] ;
int n , m ;
bool visited[maxn] ,exitfrom[maxn][maxn];
void BFS(int t){
while(!bfs.empty()){
auto [pay , ver , dir] =bfs.top();
bfs.pop() ;
//cout<<ver<<' '<<pay<<' '<<' '<<dir<<' '<<t<<" " ;
if(ver==t){
cout<<pay ;
return ;
}
if(ver+dir>=0 && ver+dir<n) bfs.push({1+pay , ver+dir , dir}) ;
if(!visited[ver]){
visited[ver]=1 ;
for(int i:doge[ver]){
//cout<<i<<' ' ;
if(ver+i<n) if(!visited[ver+i]){
bfs.push({1 + pay , ver+i , i}) ;
}
if(ver-1 >=0) if(!visited[ver-i]){
bfs.push({pay+1 , ver-i , -i}) ;
}
}
doge[ver].clear() ;
doge[ver].shrink_to_fit();
}
//cout<<bfs.size()<<'\n';
}
cout<<-1 ;
}
int main(){
cin>>n>>m ;
int loc , p;
for(int i=0 ; i<=n ;i++) doge[i].reserve(30000) ;
cin>>loc>>p ;
doge[loc].push_back(p) ;
bfs.push({0,loc,n+1}) ;
cin>>loc>>p ;
for(int i=2 ; i<m ;i++){
int loco;
cin>>loco>>p ;
doge[loco].push_back(p) ;
}
BFS(loc) ;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |