This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>g[1500005];
int n,m;
int s,t;
long long d[1500005];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int b,p;cin>>b>>p;
b++;
if(i==1)s=b;
if(i==2)t=b;
if(p>30){for(int j=b-p;j>=1;j-=p){g[b].push_back({j,(b-j)/p});}
for(int j=b+p;j<=n;j+=p){g[b].push_back({j,(j-b)/p});}
}
else
{
g[b].push_back({n+(b-1)*30+p,0});
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=30;j++)
{
g[n+(i-1)*30+j].push_back({i,0});
}
for(int i=1;i<=n;i++)
for(int j=1;j<=30;j++)
{
if(i+j<=n){
g[n+(i-1)*30+j].push_back({n+(i+j-1)*30+j,1});
g[n+(i+j-1)*30+j].push_back({n+(i-1)*30+j,1});
}
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
for(int i=1;i<=n*40;i++)d[i]=1e18;
d[s]=0;
pq.push({0,s});
//cout<<s<<endl;
//for(auto v:g[1])cout<<v.first<<endl;
while(pq.size())
{
int u=pq.top().second;
pq.pop();
for(auto v:g[u])
{
if(d[v.first]>d[u]+v.second){d[v.first]=d[u]+v.second;pq.push({d[v.first],v.first});}
}
}
if(d[t]<1e18)
cout<<d[t];
else cout<<-1;
return 0;
}
# | 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... |