Submission #668164

#TimeUsernameProblemLanguageResultExecution timeMemory
668164aebovJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
1 ms980 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define F first #define S second #define pb push_back #define endl '\n' using namespace std; const int N = 3e4+5; int b[N], p[N]; ll d[N]; vector<pii> adj[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> b[i] >> p[i]; d[i] = -1; } for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) if (i != j && abs(b[i]-b[j]) % p[i] == 0) adj[i].pb({j, abs(b[i]-b[j]) / p[i]}); priority_queue<pll, vector<pll>, greater<pll>> q; q.push({0, 1}); while (q.size()) { ll v = q.top().S, w = q.top().F; q.pop(); if (d[v] != -1) continue; d[v] = w; for (pii x : adj[v]) if(w+x.S < d[x.F])q.push({w+x.S, x.F}); } cout << d[2] << 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...