Submission #1262694

#TimeUsernameProblemLanguageResultExecution timeMemory
1262694tormentJakarta Skyscrapers (APIO15_skyscraper)C++20
36 / 100
1093 ms189816 KiB
#include <bits/stdc++.h> using namespace std; const int N = 30005; const long long inf = 1e18; set<pair<int, int>> G[N]; long long dist[N]; struct T{ int node; long long dist; bool operator<(const T& other)const{ return dist < other.dist; } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<array<int, 2>>v(m); for(int i = 0;i < m;++i){ int b, p; cin >> b >> p; v[i] = {b, p}; for(int j = b;j < n;j += p){ G[b].insert({j, (j - b) / p}); } for(int j = b;j >= 0;j -= p){ G[b].insert({j, (b - j) / p}); } } for(int i = 0;i < n;++i){ dist[i] = inf; } int s = v[0][0], t = v[1][0]; dist[s] = 0; priority_queue<T>pq; T temp = {s, dist[s]}; pq.push(temp); while(!pq.empty()){ int node = pq.top().node; long long D = pq.top().dist; pq.pop(); if(D != dist[node])continue; for(auto t : G[node]){ int v = t.first, w = t.second; if(dist[v] > dist[node] + w){ dist[v] = dist[node] + w; pq.push({v, dist[v]}); } } } if(dist[t] == inf)dist[t] = -1; cout << dist[t] << '\n'; }
#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...