Submission #914214

#TimeUsernameProblemLanguageResultExecution timeMemory
914214esomerAirplane (NOI23_airplane)C++17
0 / 100
74 ms16128 KiB
#include<bits/stdc++.h> using namespace std; #define int long long vector<int> Dijkstra(int start, vector<vector<int>>& adj, vector<int>& a){ int n = (int)adj.size(); vector<int> dist(n, 1e18); vector<bool> vis(n, false); dist[start] = 0; priority_queue<pair<int, int>> q; q.push({0, start}); while(!q.empty()){ int x = q.top().second; q.pop(); if(vis[x]) continue; vis[x] = true; for(int& node : adj[x]){ if(dist[node] > max(a[node], dist[x] + 1)){ dist[node] = max(a[node], dist[x] + 1); q.push({-dist[node], node}); } } } return dist; } void solve(){ int n, m; cin >> n >> m; vector<int> a(n); for(auto &i : a) cin >> i; vector<vector<int>> adj(n); for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--; v--; adj[u].push_back(v); adj[v].push_back(u); } vector<int> dist1 = Dijkstra(0, adj, a); vector<int> distN = Dijkstra(n-1, adj, a); int ans = 1e18; for(int i = 0; i < n; i++){ int cost = max(dist1[i], distN[i]) * 2; if(abs(dist1[i] - distN[i]) == 1 && min(dist1[i], distN[i]) >= 1) cost--; ans = min(ans, cost); } cout << ans << "\n"; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); // int tt; cin >> tt; int tt = 1; while(tt--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...