Submission #1193105

#TimeUsernameProblemLanguageResultExecution timeMemory
1193105loomAirplane (NOI23_airplane)C++20
100 / 100
237 ms27272 KiB
#include<bits/stdc++.h> #define loop(a,b,c,d) for(int a=b; a<c; a+=d) #define loop2(a,b,c,d) for(int a=b; a>=c; a-=d) #define bl(i,n) loop(i,0,n,1) #define bl2(i,n) loop2(i,n,0,1) #define int long long #define nl endl #define g ' ' using namespace std; vector<int> graph[200001]; int h[200001]; vector<int> Dijkstra(int src){ priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq; pq.push(make_pair(0, src)); vector<int> dist(200001, 1e18); dist[src] = 0; vector<int> vis(200001, 0); while(!pq.empty()){ int v = pq.top().second; pq.pop(); if(vis[v]) continue; vis[v] = 1; for(int ch : graph[v]){ if(max(dist[v]+1, h[ch]) < dist[ch]){ dist[ch] = max(dist[v]+1, h[ch]); pq.push(make_pair(dist[ch], ch)); } } } return dist; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL); int n, m; cin>>n>>m; bl(i,n) cin>>h[i+1]; bl(_,m){ int a, b; cin>>a>>b; graph[a].push_back(b); graph[b].push_back(a); } auto dist1 = Dijkstra(1); auto dist2 = Dijkstra(n); int ans = 1e18; for(int node=1; node<=n; node++){ ans = min(ans, max(dist1[node], dist2[node])*2); for(int ch : graph[node]){ ans = min(ans, max(dist1[node], dist2[ch])*2+1); ans = min(ans, max(dist1[ch], dist2[node])*2+1); } } cout<<ans; 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...