Submission #1275323

#TimeUsernameProblemLanguageResultExecution timeMemory
1275323sh1ftAirplane (NOI23_airplane)C++17
22 / 100
155 ms14480 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int mxN = 2e5+5; int n, m; ll a[mxN], dis[mxN], ans = LLONG_MAX; vector <int> adj[mxN]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 0, u, v; i < m; i++) cin >> u >> v, adj[u].emplace_back(v), adj[v].emplace_back(u); priority_queue <tuple <ll, ll, ll, int>> q; q.emplace(0, 0, 0, 1); for (int i = 2; i <= n; i++) dis[i] = LLONG_MAX; while (!q.empty()) { auto [t, L, R, u] = q.top(); q.pop(); if (u == n) { ans = min(ans, (-t) + R); continue; } for (auto v : adj[u]) { ll w = 1, l = L+1, r = R; if (a[v] > l) w += a[v] - l, l = a[v]; r--; r = max(r, a[v]); if (dis[v] > dis[u] + w) q.emplace(-(dis[v] = dis[u] + w), l, r, v); } } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...