Submission #1105604

#TimeUsernameProblemLanguageResultExecution timeMemory
110560412345678Airplane (NOI23_airplane)C++17
0 / 100
1062 ms21300 KiB
#include <bits/stdc++.h> using namespace std; const int nx=2e5+5; int n, m, a[nx], u, v, vl[nx], rvl[nx], vs[nx], dist[nx], res=1e9; vector<int> d[nx]; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>m; for (int i=1; i<=n; i++) cin>>a[i], vl[i]=rvl[i]=1e9; for (int i=1; i<=m; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u); vl[1]=rvl[n]=0; pq.push({0, 1}); while (!pq.empty()) { auto [cw, u]=pq.top(); pq.pop(); if (vs[u]) continue; vs[u]=1; for (auto v:d[u]) if (vl[v]>max(cw+1, a[v])) vl[v]=max(cw+1, a[v]), pq.push({vl[v], v}); } pq.push({0, n}); for (int i=1; i<=n; i++) vs[i]=0; while (!pq.empty()) { auto [cw, u]=pq.top(); pq.pop(); if (vs[u]) continue; vs[u]=1; for (auto v:d[u]) if (rvl[v]>max(cw+1, a[v])) rvl[v]=max(cw+1, a[v]), pq.push({vl[v], v}); } for (int t=1; t<=n; t++) { int mx=a[t]; for (int i=1; i<=n ;i++) dist[i]=1e9, vs[i]=0; for (int i=1; i<=n; i++) if (vl[i]<=mx) dist[i]=0, pq.push({0, i}); while (!pq.empty()) { auto [cw, u]=pq.top(); pq.pop(); if (vs[u]) continue; vs[u]=1; for (auto v:d[u]) if (a[v]<=mx&&dist[v]>cw+1) dist[v]=cw+1, pq.push({dist[v], v}); } for (int i=1; i<=n; i++) if (rvl[i]<=mx) res=min(res, 2*mx+dist[i]); } cout<<res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...