Submission #1102766

#TimeUsernameProblemLanguageResultExecution timeMemory
1102766ttamxAirplane (NOI23_airplane)C++17
0 / 100
55 ms16380 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const int N=2e5+5; const int INF=INT_MAX/2; int n,m; int a[N]; vector<int> adj[N]; int dist1[N],dist2[N]; int ans=INF; void dijkstra(int st,int *dist){ priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; for(int i=1;i<=n;i++)dist[i]=INF; dist[st]=0; pq.emplace(0,st); while(!pq.empty()){ auto [d,u]=pq.top(); pq.pop(); if(d>dist[u])continue; for(auto v:adj[u]){ int nd=max(d+1,a[v]); if(nd<dist[v]){ dist[v]=nd; pq.emplace(nd,v); } } } } int main(){ cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> m; for(int i=1;i<=n;i++)cin >> a[i]; for(int i=0;i<m;i++){ int u,v; cin >> u >> v; adj[u].emplace_back(v); adj[v].emplace_back(u); } dijkstra(1,dist1); dijkstra(n,dist2); for(int i=1;i<=n;i++){ int mx=max(dist1[i],dist2[i]); ans=min(ans,mx*2-(mx>a[i])); } 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...