Submission #1112979

#TimeUsernameProblemLanguageResultExecution timeMemory
1112979AvianshAirplane (NOI23_airplane)C++17
0 / 100
1100 ms15816 KiB
#include <bits/stdc++.h> using namespace std; int n,m; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; int a[n]; for(int &i : a){ cin >> i; } vector<int>g[n]; for(int i = 0;i<m;i++){ int a,b; cin >> a >> b; a--;b--; g[a].push_back(b); g[b].push_back(a); } set<array<int,3>>pq; pq.insert({0,0,0}); //time,current height, place, downbool set<array<int,2>>vis; vis.insert({0,0}); //height,place,downbool long long ans = 0; while(!pq.empty()){ array<int,3>cur = *(pq.begin()); //cout << cur[0] << " " << cur[1] << " " << cur[2] << " " << cur[3] << "\n"; pq.erase(pq.begin()); if(cur[1]>2000){ continue; } if(cur[1]==0&&cur[2]==n-1){ ans=cur[0]; break; } pq.insert({cur[0]+1,cur[1]+1,cur[2]}); if(cur[1]>a[cur[2]]){ pq.insert({cur[0]+1,cur[1]-1,cur[2]}); } for(int i : g[cur[2]]){ if(cur[1]-1>=a[i]&&vis.find({cur[1]-1,i})==vis.end()){ pq.insert({cur[0]+1,cur[1]-1,i}); vis.insert({cur[1]-1,i}); } if(cur[1]>=a[i]&&vis.find({cur[1],i})==vis.end()){ pq.insert({cur[0]+1,cur[1],i}); vis.insert({cur[1],i}); } if(cur[1]+1>=a[i]&&vis.find({cur[1]+1,i})==vis.end()){ pq.insert({cur[0]+1,cur[1]+1,i}); vis.insert({cur[1]+1,i}); } } } 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...