제출 #666187

#제출 시각아이디문제언어결과실행 시간메모리
666187KahouJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
387 ms68168 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define mk make_pair #define endl '\n' typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const ll inf = 1e18 + 50; const int N = 2050, M = 30050; ll n, m, b[M], p[M], dis[N]; ll adj[N][N]; set<pll> st; void solve() { cin >> n >> m; for (int x = 0; x < n; x++) { dis[x] = inf; for (int y = 0; y < n; y++) { if (x == y) continue; adj[x][y] = inf; } } for (int i = 0; i < m; i++) { cin >> b[i] >> p[i]; for (int x = b[i]%p[i]; x < n; x += p[i]) { adj[b[i]][x] = min(adj[b[i]][x], abs(x-b[i])/p[i]); } } dis[b[0]] = 0; st.insert({dis[b[0]], b[0]}); while (st.size()) { int u = st.begin()->S; st.erase(st.begin()); for (int v = 0; v < n; v++) { if (dis[u] + adj[u][v] < dis[v]) { st.erase({dis[v], v}); dis[v] = dis[u] + adj[u][v]; st.insert({dis[v], v}); } } } cout << (dis[b[1]] >= inf? -1: dis[b[1]]) << endl; } int main() { ios::sync_with_stdio(0), cin.tie(0); solve(); 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...