Submission #671633

#TimeUsernameProblemLanguageResultExecution timeMemory
671633Radin_Zahedi2Jakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
36 ms16144 KiB
#include<bits/stdc++.h> //#pragma GCC optimize("O2") using namespace std; using ll = long long; using ld = long double; #define pb push_back #define mp make_pair #define fi first #define se second #define sz(x) (int)x.size() #define endl '\n' const int mod = 1e9 + 7; const int inf = 1e9 + 5; const ll linf = 9e18 + 5; int n, m; const int N = 2e3 + 5; int arr[N][2]; int w[N][N]; int dist[N]; void init() { } void input() { cin >> m >> n; for (int i = 1; i <= n; i++) { cin >> arr[i][0] >> arr[i][1]; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (abs(arr[j][0] - arr[i][0]) % arr[i][1] == 0) { w[i][j] = abs(arr[j][0] - arr[i][0]) / arr[i][1]; } else { w[i][j] = inf; } } } } void dijk() { set<pair<int, int>> dists; for (int i = 1; i <= n; i++) { dist[i] = inf; dists.insert(mp(dist[i], i)); } dists.erase(mp(dist[1], 1)); dist[1] = 0; dists.insert(mp(dist[1], 1)); while (!dists.empty()) { int u = dists.begin()->se; dists.erase(dists.begin()); for (int v = 1; v <= n; v++) { if (dist[v] > dist[u] + w[u][v]) { dists.erase(mp(dist[v], v)); dist[v] = dist[u] + w[u][v]; dists.insert(mp(dist[v], v)); } } } } void solve() { dijk(); if (dist[2] == inf) { cout << -1; } else { cout << dist[2]; } } void output() { } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int number_of_testcases = 1; //cin >> number_of_testcases; while (number_of_testcases--) { init(); input(); solve(); output(); } 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...