Submission #409734

#TimeUsernameProblemLanguageResultExecution timeMemory
409734nicholaskJakarta Skyscrapers (APIO15_skyscraper)C++14
10 / 100
1 ms296 KiB
#include <bits/stdc++.h> #define int long long #define double long double #define x first #define y second #define pb push_back #define rt return using namespace std; signed main(){ int n,m; cin>>n>>m; vector <pair <int,int> > g[n]; pair <int,int> a[m]; for (int i=0; i<m; i++){ cin>>a[i].x>>a[i].y; for (int j=1; a[i].x-a[i].y*j>=0; j++){ g[a[i].x].pb({a[i].x-a[i].y*j,j}); } for (int j=1; a[i].x+a[i].y*j<n; j++){ g[a[i].x].pb({a[i].x+a[i].y*j,j}); } } priority_queue <pair <int,int>,vector <pair <int,int> >,greater <pair <int,int> > > pq; bool visited[n]; for (int i=0; i<n; i++) visited[i]=0; int dist[n]; for (int i=0; i<n; i++) dist[i]=1e18; dist[a[0].x]=0; pq.push({a[0].x,0}); while (!pq.empty()){ pair <int,int> tp=pq.top(); pq.pop(); if (visited[tp.y]) continue; visited[tp.y]=1; for (auto&i:g[tp.y]){ if (!visited[i.x]&&tp.x+i.y<dist[i.x]){ dist[i.x]=tp.x+i.y; pq.push({dist[i.x],i.x}); } } } if (dist[a[1].x]==1e18) cout<<"-1\n"; else cout<<dist[a[1].x]<<endl; }
#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...