// In The Name Of God
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define pb push_back
#define endl '\n'
#define test(x) cout<<x,exit(0)
#define fast (ios_base::sync_with_stdio(false),cin.tie(NULL))
const int maxn=3e4+10;
const int inf=1e9;
const int sq=250;
int mark[maxn][sq+5];
int dis[maxn];
vector<int>vec[maxn];
int n,m;
int main(){
fast;
cin>>n>>m;
int start,en;
for(int i=1;i<=m;i++){
int b,p;cin>>b>>p;
if(i==1){
start=b;
}
if(i==2){
en=b;
}
vec[b].pb(p);
}
for(int i=0;i<n;i++){
dis[i]=inf;
}
dis[start]=0;
priority_queue<pii, vector<pii>, greater<pii>> st;
st.push({0,start});
while(st.size()){
int d=st.top().first;
int v=st.top().second;
st.pop();
if(dis[v]<d){
continue;
}
for(int ind=0;ind<vec[v].size();ind++){
int p=vec[v][ind];
int cnt=1;
for(int i=v+p;i<n;i+=p){
if(dis[i]>dis[v]+cnt){
dis[i]=dis[v]+cnt;
st.push({dis[i],i});
}
cnt++;
}
cnt=1;
for(int i=v-p;i>=0;i-=p){
if(dis[i]>dis[v]+cnt){
dis[i]=dis[v]+cnt;
st.push({dis[i],i});
}
cnt++;
}
}
}
if(dis[en]>1e7){
cout<<-1<<endl;
}
else{
cout<<dis[en]<<endl;
}
}
# | 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... |