Submission #1264425

#TimeUsernameProblemLanguageResultExecution timeMemory
1264425AutoratchJakarta Skyscrapers (APIO15_skyscraper)C++20
0 / 100
1 ms1096 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int n,m; int b[30010],p[30010],dp[30010]; int dist[30010]; vector<pair<int,int>> v[30010]; priority_queue<pair<int,int>> pq; signed main(){ cin>>n>>m; for(int i=0;i<m;i++){ cin>>b[i]>>p[i]; } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i==j) continue; if(abs(b[j]-b[i])%p[i]==0){ v[i].push_back({j,abs(b[j]-b[i])/p[i]}); } } } for(int i=1;i<m;i++) dist[i]=INT_MAX; pq.push({0,0}); while(pq.empty()==0){ int w=-pq.top().first; int u=pq.top().second; if(u==1){ cout<<w; return 0; } pq.pop(); for(auto p: v[u]){ if(w+p.second<dist[p.first]){ pq.push({-w-p.second,p.first}); dist[p.first]=w+p.second; } } } cout<<"-1"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...