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;
int n,p[30004],b[30004],m;
priority_queue <pair<int,int> ,vector <pair<int,int> >,greater <pair<int,int> > > pq;
bool vis[30004];
vector <int> v[30004];
int cur[30004];
void dij()
{
for (int i=1;i<n;i++)
cur[i]=INT_MAX;
for (int i=0;i<v[b[0]].size();i++)
cur[v[b[0]][i]]=0,pq.push({0,v[b[0]][i]});
while (!pq.empty())
{
int x= (pq.top()).second;
int y= (pq.top()).first;
pq.pop();
if (vis[x])
continue;
vis[x]=true;
for (int i=0;i*p[x]+b[x]<n;i++)
{
int a= (i*p[x]+b[x]);
for (int j=0;j<v[a].size();j++)
{
if (cur[v[a][j]]>i+y)
{
pq.push({i+y,v[a][j]});
cur[v[a][j]]=i+y;
}
}
}
for (int i=1;b[x]-i*p[x]>=0;i++)
{
int a= (b[x]-i*p[x]);
for (int j=0;j<v[a].size();j++)
{
if (cur[v[a][j]]>i+y)
{
pq.push({i+y,v[a][j]});
cur[v[a][j]]=i+y;
}
}
}
}
}
int main()
{
cin >>n>>m;
for (int i=0;i<m;i++)
{
cin >>b[i]>>p[i];
v[b[i]].push_back(i);
}
dij();
if (cur[1]==INT_MAX)
cout <<-1;
else
cout <<cur[1];
return 0;
}
Compilation message (stderr)
skyscraper.cpp: In function 'void dij()':
skyscraper.cpp:12:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[b[0]].size();i++)
^
skyscraper.cpp:25:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0;j<v[a].size();j++)
^
skyscraper.cpp:37:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0;j<v[a].size();j++)
^
# | 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... |