제출 #1317867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317867		vedchoudhary	Airplane (NOI23_airplane)	C++20	22 / 100	51 ms	15904 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

using ll = long long;
#define int ll

const int INF = (ll)4e18;
int n;
vector<vector<int>> adj;
vector<int> a;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int m; cin >> n >> m;
    adj = vector<vector<int>>(n);
    a = vector<int>(n); for(int& i : a) cin >> i;
    for(int i = 0; i < m; i++) {
        int a,b; cin >> a >> b; a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> dist(n,INF);
    vector<int> minA(n);

    priority_queue<array<int,3>, vector<array<int,3>>, greater<array<int,3>>> pq;
    pq.push({0,0});

    while(!pq.empty()) {
        auto [d,mn,curr] = pq.top(); pq.pop();
        if(d>dist[curr]) continue;
        dist[curr] = max(a[curr],d);
        minA[curr] = max(a[curr],mn);
        for(int nxt : adj[curr]) {
            pq.push({dist[curr]+1,minA[curr]-1,nxt});
        }
    }

    cout << dist[n-1]+minA[n-1];

    return 0;
}

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