Submission #1173724

#TimeUsernameProblemLanguageResultExecution timeMemory
1173724somefolkAirplane (NOI23_airplane)C++20
100 / 100
220 ms34032 KiB
#include <iostream> #include <cmath> #include <algorithm> #include <string> #include <vector> #include <map> #include <unordered_map> #include <queue> #include <set> #include <unordered_set> #include <complex> #include <list> #include <cassert> #include <chrono> #include <random> #include <stack> #include <iomanip> #include <fstream> using namespace std; #define endl "\n" #define int long long const int INF = 1e9+7; const int MOD = 1e9+7; int n, m; vector<vector<pair<int, int>>> adj; vector<int> dijkstra(int s){ vector<int> dist(n+1, INF); vector<bool> vis(n+1, false); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; dist[s] = 0; pq.push({0, s}); while(!pq.empty()){ int u = pq.top().second; pq.pop(); if(vis[u]) continue; vis[u] = true; for(auto &i : adj[u]){ int v = i.first, w = i.second; if(dist[v] > max(w, dist[u] + 1)){ dist[v] = max(w, dist[u] + 1); pq.push({dist[v], v}); } } } return dist; } void solve(){ cin >> n >> m; vector<int> a(n+1); for(int i = 1; i <= n; i++){ cin >> a[i]; } adj.resize(n+1); for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; adj[u].push_back({v, a[v]}); adj[v].push_back({u, a[u]}); } vector<int> dist1 = dijkstra(1); vector<int> dist2 = dijkstra(n); int sol = INF; for(int i = 1; i <= n; i++){ sol = min(sol, max(dist1[i], dist2[i])*2); for(auto &j : adj[i]){ sol = min(sol, max(dist1[i], dist2[j.first])*2+1); sol = min(sol, max(dist1[j.first], dist2[i])*2+1); } } cout << sol << endl; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while(t--) 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...