제출 #1102328

#제출 시각아이디문제언어결과실행 시간메모리
1102328HiepVu217Airplane (NOI23_airplane)C++17
100 / 100
288 ms28348 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 17; const long long oo = 1e18; int n, m, a[N]; vector <int> adj[N]; long long ds[N], dt[N], ans; void dijkstra (int s, long long d[]) { priority_queue <pair <long long, int>> pq; for (int i = 1; i <= n; ++i) { d[i] = oo; } d[s] = 0; pq.push({0, s}); while (!pq.empty()) { auto [du, u] = pq.top(); du = -du; pq.pop(); if (du > d[u]) { continue; } for (int v: adj[u]) { long long z = max (1LL * a[v], du + 1); if (z < d[v]) { d[v] = z; pq.push({-z, v}); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1, u, v; i <= m; ++i) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } dijkstra (1, ds); dijkstra (n, dt); ans = oo; for (int i = 1; i <= n; ++i) { ans = min (ans, max (ds[i], dt[i]) * 2); for (int j: adj[i]) { ans = min (ans, max (ds[i], dt[j]) * 2 + 1); } } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...