| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 981423 | Faisal_Saqib | Jakarta Skyscrapers (APIO15_skyscraper) | C++17 | 0 ms | 0 KiB |
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 <iostream>
#include <set>
#include <vector>
using namespace std;
const int NP=3e4+10;
const int NP1=3e4+10;
const long long inf=1e18;
long long dist[NP1];
int b[NP],p[NP];
vector<int> len[NP1];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int j=0;j<n;j++)
dist[j]=inf;
for(int j=0;j<m;j++)
{
cin>>b[j]>>p[j];
len[b[j]].push_back(p[j]);
}
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> dp;
dp.push({0,b[0]});
dist[b[0]]=0;
while(dp.size())
{
auto f=(dp.top());
dp.pop();
if(f.second==b[1])
{
cout<<f.first<<'\n';
break;
}
for(auto lp:len[f.second])
{
int po=f.second+lp;
int le=1;
while(po<n)
{
if(dist[po]>f.first+le)
{
dist[po]=f.first+le;
dp.push({dist[po],po});
}
po+=lp;
le++;
}
po=f.second-lp;
le=1;
while(po>=0)
{
if(dist[po]>f.first+le)
{
dist[po]=f.first+le;
dp.push({dist[po],po});
}
po-=lp;
le++;
}
}
}
if(dist[b[1]]==inf)
cout<<-1<<'\n';
return 0;
}