제출 #350631

#제출 시각아이디문제언어결과실행 시간메모리
350631FischerJakarta Skyscrapers (APIO15_skyscraper)C++14
0 / 100
3 ms2668 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 3e4 + 10; set<int> pos[maxn]; vector<pair<int, int>> g[maxn]; using ll = long long; ll d[maxn]; ll dijkstra(int src, int snk) { memset(d, 1, sizeof d); d[src] = 0; using pii = pair<ll, int>; priority_queue<pii, vector<pii>, greater<pii>> Q; Q.push({0, src}); while (!Q.empty()) { auto q = Q.top(); Q.pop(); if (q.second == snk) return q.first; if (q.first != d[q.second]) continue; for (auto e : g[q.second]) { ll temp = q.first + e.second; if (temp < d[e.first]) { d[e.first] = temp; Q.push({temp, e.first}); } } } return -1; } int main() { int n, m; cin >> n >> m; vector<pair<int, int>> a; set<pair<int, int>> t; for (int i = 0; i < m; ++i) { int b, p; cin >> b >> p; t.insert({p, b}); pos[b].insert(p); } auto same = [](int b, int p) { return !pos[b].empty() && pos[b].count(p); }; for (auto q : t) { for (int i = 1; ; ++i) { int temp = q.second + i * q.first; if (temp >= n) break; g[q.second].emplace_back(temp, i); if (same(temp, q.first)) break; } for (int i = 1; ; ++i) { int temp = q.second - i * q.first; if (temp < 0) break; g[q.second].emplace_back(temp, i); if (same(temp, q.first)) break; } } cout << dijkstra(0, 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...