Submission #1205390

#TimeUsernameProblemLanguageResultExecution timeMemory
1205390biankAirplane (NOI23_airplane)C++20
0 / 100
51 ms21516 KiB
#include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<int(n);i++) #define forsn(i,s,n) for(int i=int(s);i<int(n);i++) #define dforn(i,n) for(int i=int(n)-1;i>=0;i--) #define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--) #define fst first #define snd second #define pb push_back #define eb emplace_back #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() typedef long long ll; typedef vector<ll> vll; typedef vector<int> vi; typedef pair<int,int> ii; const ll INF=1e18; pair<vll,vll> dijkstra(int s, vector<vi> &adj, vi &a){ int n=sz(adj); vll dist(n,INF); vll height(n,INF); priority_queue<tuple<ll,int,int>> pq; pq.emplace(0,0,s); dist[s]=0,height[s]=0; vector<bool> vis(n,false); while(!pq.empty()){ auto[d,h,u]=pq.top(); pq.pop(); for(int v:adj[u]){ ll newH=max(h,a[v]); ll newD=dist[u]+max(newH-h,1LL); if(make_pair(-newD,-newH)>make_pair(-dist[v],-height[v])){ dist[v]=newD,height[v]=newH; pq.emplace(-dist[v],height[v],v); } } } return {dist,height}; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m; cin>>n>>m; vi a(n); forn(i,n) cin>>a[i]; vector<vi> adj(n); forn(i,m){ int u,v; cin>>u>>v; --u,--v; adj[u].pb(v); adj[v].pb(u); } auto[distFromS,heightFromS]=dijkstra(0,adj,a); auto[distToT,heightToT]=dijkstra(n-1,adj,a); ll res=INF; forn(u,n){ ll curr=max(distFromS[u],heightToT[u])+max(distToT[u],heightFromS[u]); res=min(res,curr); curr=distFromS[u]+distToT[u]+abs(heightToT[u]-heightFromS[u]); res=min(res,curr); for(int v:adj[u]){ curr=max(distFromS[u],heightToT[v])+max(distToT[v],heightFromS[u])+1; res=min(res,curr); curr=distFromS[u]+distToT[v]+abs(heightToT[v]-heightFromS[u])+1; res=min(res,curr); } } cout<<res<<'\n'; 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...