제출 #602733

#제출 시각아이디문제언어결과실행 시간메모리
602733promaJakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
1095 ms65500 KiB
#include <bits/stdc++.h> #define int long long #define see(x) cout<<#x<<"="<<x<<endl; #define endl "\n" using namespace std; const int N = 30005; const int INF = 1e18; int n, m, b[N], p[N], d[N]; vector <pair <int, int>> g[N]; priority_queue <pair <int, int>> q; map <int, vector <int>> mp; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); /* freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); */ cin >> n >> m; for (int i = 0; i < m; i ++) { cin >> b[i] >> p[i]; mp[b[i]].push_back(i); } for (int i = 0; i < m; i ++) { for (int j = 0; j < n; j ++) { for (auto k: mp[j]) { if (k == i) continue; if (abs(b[k] - b[i]) % p[i] == 0) g[i].push_back({k, abs(b[k] - b[i]) / p[i]}); } } } for (int i = 0; i < m; i ++) { d[i] = INF; } d[0] = 0; q.push({0, 0}); while (!q.empty()) { int v = q.top().second; q.pop(); for (auto i: g[v]) { if (d[i.first] > d[v] + i.second) { d[i.first] = d[v] + i.second; q.push({-d[i.first], i.first}); } } } if (d[1] == INF) d[1] = -1; cout << d[1] << endl; return 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...