#include <bits/stdc++.h> using namespace std; #define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define fi first #define se second #define debug(x) cerr << " - " << #x << ": " << x << endl; #define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl; #define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl; #define sep() cerr << "--------------------" << endl; #define all(x) (x).begin(),(x).end() #define sz(x) (ll)x.size() #define ll long long #define int ll #define ii pair<int,int> #define v vector<int> #define vii vector<ii> #define vv vector<vector<int> > #define mp make_pair #define INF 100000000000 #define pb push_back #define EPS 1e-9 const int MOD = 1000000007; // 998244353 int B[300005],P[300005]; int dist[2005][2005]; bool vis[300005]; vv vec; main(){ boost; int N,M; cin>>N>>M; vec.resize(N); for (int i = 0; i < M; ++i){ cin>>B[i]>>P[i]; vec[B[i]].pb(i); } for (int i = 0; i < N; ++i){ for (int j = 0; j <= 2000; ++j) { dist[i][j]=INF; } } //dist[i]=INF; vis[B[0]]=1; queue<pair<int,ii> > pq; for (int i = 0; i < sz(vec[B[0]]); ++i){ dist[B[0]][P[vec[B[0]][i]]]=0; pq.push({0,{B[0],vec[B[0]][i]}}); } while(!pq.empty()){ pair<int,ii> front=pq.front(); pq.pop(); if(front.se.fi==B[1]){ cout<<front.fi<<"\n"; return 0; } //if(dist[front.se.fi][P[front.se.se]]<front.fi)continue; //debugii(front.se); //debug(front.fi); //sep() int idx=front.se.fi+P[front.se.se]; if(idx<N){ if(dist[idx][P[front.se.se]]>dist[front.se.fi][P[front.se.se]]+1){ dist[idx][P[front.se.se]]=dist[front.se.fi][P[front.se.se]]+1; pq.push({dist[idx][P[front.se.se]],{idx,front.se.se}}); } if(!vis[idx]){ for (int i = 0; i < sz(vec[idx]); ++i){ dist[idx][P[vec[idx][i]]]=dist[front.se.fi][P[front.se.se]]+1; pq.push({dist[idx][P[vec[idx][i]]],{idx,vec[idx][i]}}); } vis[idx]=1; } } idx=front.se.fi-P[front.se.se]; if(idx>=0){ if(dist[idx][P[front.se.se]]>dist[front.se.fi][P[front.se.se]]+1){ dist[idx][P[front.se.se]]=dist[front.se.fi][P[front.se.se]]+1; //debug(1); pq.push({dist[idx][P[front.se.se]],{idx,front.se.se}}); } if(!vis[idx]){ for (int i = 0; i < sz(vec[idx]); ++i){ dist[idx][P[vec[idx][i]]]=dist[front.se.fi][P[front.se.se]]+1; pq.push({dist[idx][P[vec[idx][i]]],{idx,vec[idx][i]}}); } vis[idx]=1; } } } cout<<-1; cout<<"\n"; return 0; } //long long //array bounds //special cases //binary search

skyscraper.cpp:27:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^