Submission #443792

#TimeUsernameProblemLanguageResultExecution timeMemory
443792impriJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
875 ms64580 KiB
#include<bits/stdc++.h> using namespace std; long long graph[2001][2001]; int main(void){ int n,m; int arr[30001][2]; cin >> n >> m; for(int i=0;i<m;i++) cin >> arr[i][0] >> arr[i][1]; for(int i=0;i<n;i++) for(int j=0;j<n;j++) graph[i][j]=10e13; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(abs(arr[i][0]-j)%arr[i][1]==0){ graph[arr[i][0]][j]=min(graph[arr[i][0]][j],1LL*abs(arr[i][0]-j)/arr[i][1]); } } } long long dist[2001]; for(int i=0;i<n;i++) dist[i]=10e14; dist[arr[0][0]]=0; priority_queue<pair<long long,int> >q; q.push({0,arr[0][0]}); while(!q.empty()){ int cur=q.top().second; long long curdist=-q.top().first; q.pop(); for(int i=0;i<n;i++){ long long nxtdist=graph[cur][i]; if(curdist+nxtdist<dist[i]){ dist[i]=curdist+nxtdist; q.push({-dist[i],i}); } } } if(dist[arr[1][0]]>10e12)cout << -1; else cout << dist[arr[1][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...