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>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=30005;
int n,m,b[N],p[N],d[N];
vector<pii>adj[N];
set<int>have[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>b[i]>>p[i];
b[i]++;
have[b[i]].insert(p[i]);
}
for(int i=1;i<=m;i++)
{
int cur=b[i];
int cnt=0;
while(cur+p[i]<=n)
{
cnt++;
cur+=p[i];
adj[b[i]].push_back(mp(cur,cnt));
if(have[cur].find(p[i])!=have[cur].end()) break;
}
cur=b[i];
cnt=0;
while(cur-p[i]>=1)
{
cnt++;
cur-=p[i];
adj[b[i]].push_back(mp(cur,cnt));
if(have[cur].find(p[i])!=have[cur].end()) break;
}
}
memset(d,-1,sizeof d);
d[b[1]]=0;
priority_queue<pii,vector<pii>,greater<pii>>pq;
pq.push(mp(0,b[1]));
while(!pq.empty())
{
auto u=pq.top();
pq.pop();
if(u.fi!=d[u.se]) continue;
for(auto&v:adj[u.se])
{
if(d[v.fi]==-1||d[v.fi]>u.fi+v.se)
{
d[v.fi]=u.fi+v.se;
pq.push(mp(d[v.fi],v.fi));
}
}
}
cout<<d[b[2]];
}
# | 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... |