Submission #914215

#	Time	Username	Problem	Language	Result	Execution time	Memory
914215		esomer	Airplane (NOI23_airplane)	C++17	100 / 100	475 ms	32340 KiB

Main

#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) 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();
}

• Subtask 1: 22 / 22
• Subtask 2: 10 / 10
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37