Submission #1102439

#TimeUsernameProblemLanguageResultExecution timeMemory
1102439SoMotThanhXuanAirplane (NOI23_airplane)C++17
100 / 100
272 ms26420 KiB
#include <bits/stdc++.h> using namespace std; const int maxN = 4e5 + 5; const int INF = 1e9; int N, M, a[maxN]; vector<int> adj[maxN]; pair<int, int> edge[maxN]; int f[maxN], g[maxN]; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q; void dijsktra(int s, int d[]){ for(int i = 1; i <= N; ++i)d[i] = INF; d[s] = 0; Q.push({0, s}); while(!Q.empty()){ int dist = Q.top().first; int u = Q.top().second; Q.pop(); if(dist > d[u])continue; for(int v : adj[u]){ int w = max(a[v], dist + 1); if(w < d[v]){ d[v] = w; Q.push({w, v}); } } } } int main(){ ios_base::sync_with_stdio(false); 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); edge[i] = make_pair(u, v); } dijsktra(1, f); dijsktra(N, g); int res = INF; for(int i = 1; i <= N; ++i){ res = min(res, f[i] + g[i] + abs(f[i] - g[i])); } for(int i = 1; i <= M; ++i){ int u = edge[i].first, v = edge[i].second; if(f[u] == g[v])res = min(res, f[u] + g[v] + 1); if(f[v] == g[u])res = min(res, f[v] + g[u] + 1); } cout << res; 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...