Submission #1112901

#TimeUsernameProblemLanguageResultExecution timeMemory
1112901AvianshAirplane (NOI23_airplane)C++17
0 / 100
1102 ms39924 KiB
#include <bits/stdc++.h> using namespace std; signed main(){ ios::sync_with_stdio(0); cin.tie(0); int n,m; 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,2>>vis; priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>>pq; pq.push({0,0,0}); long long ans = 0; while(!pq.empty()){ array<int,3>cur = pq.top(); pq.pop(); if(vis.find({cur[1],cur[2]})!=vis.end()) continue; if(cur[1]==0&&cur[2]==n-1){ ans=cur[0]; break; } int cura = cur[1]; if(cura>a[cur[2]]){ if(vis.find({a[cur[2]],cur[2]})==vis.end()) pq.push({cur[0]+cura-a[cur[2]],a[cur[2]],cur[2]}); } vis.insert({cur[1],cur[2]}); for(int i : g[cur[2]]){ if(cura+1>=a[i]){ if(vis.find({cura+1,i})==vis.end()) pq.push({cur[0]+1,cura+1,i}); } else{ if(vis.find({a[i],i})==vis.end()) pq.push({a[i]-cura+cur[0],a[i],i}); } if(cura-1>=a[i]){ if(vis.find({cura-1,i})==vis.end()) pq.push({cur[0]+1,cura-1,i}); } if(cura>=a[i]){ if(vis.find({cura,i})==vis.end()) pq.push({cur[0]+1,cura,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...