Submission #966827

#TimeUsernameProblemLanguageResultExecution timeMemory
966827elesisJakarta Skyscrapers (APIO15_skyscraper)C++14
36 / 100
123 ms262144 KiB
#include <bits/stdc++.h> #include <iomanip> using namespace std; #define int long long #define pii pair<int,int> #define ff first #define ss second #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); const int mod=1e9+7; const int inf=1e18+7; const int ninf=(-1)*inf; const int N=2e3+7; vector <pii> adj[N]; void solve() { int n,m; cin>>n>>m; vector <int> b(m),p(m); for(int i=0;i<m;i++) { cin>>b[i]>>p[i]; } vector <vector <int>> dist(m,vector <int>(m,inf)); for(int i=0;i<m;i++) { for(int j=0;j<m;j++) { if(i==j) { dist[i][i] = 0; continue; } if(abs(b[i]-b[j])%p[i]==0) { dist[i][j] = min(dist[i][j],abs(b[i]-b[j])/p[i]); adj[i].push_back({j,dist[i][j]}); } } } vector <int> d(m,inf); d[0] = 0; priority_queue <pii,vector <pii> , greater <pii>> pq; pq.push({0,0}); while(!pq.empty()) { pii cur = pq.top(); pq.pop(); int u = cur.ss; int du = cur.ff; for(auto it:adj[u]) { if(du + it.ss < d[it.ff]) { d[it.ff] = du + it.ss; pq.push({d[it.ff],it.ff}); } } } if(d[1] == inf) { cout << -1 << "\n"; return; } cout << d[1] << "\n"; } signed main(){ fast int t=1; //cin>>t; while(t--) solve(); }
#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...