제출 #1358751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358751		bakhtiyarn	Airplane (NOI23_airplane)	C++20	100 / 100	185 ms	24676 KiB

Main

// GPT
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
static const ll INF = (1LL << 62);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<vector<int>> adj(n + 1);
    vector<pair<int,int>> edges;
    edges.reserve(m);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges.push_back({u, v});
    }

    auto dijkstra = [&](int src) {
        vector<ll> dist(n + 1, INF);
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;

        dist[src] = 0;
        pq.push({0, src});

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d != dist[u]) continue;

            for (int v : adj[u]) {
                ll nd = max(d + 1, a[v]);
                if (nd < dist[v]) {
                    dist[v] = nd;
                    pq.push({nd, v});
                }
            }
        }
        return dist;
    };

    vector<ll> d1 = dijkstra(1);
    vector<ll> d2 = dijkstra(n);

    ll ans = INF;

    for (int i = 1; i <= n; ++i) {
        ans = min(ans, 2 * max(d1[i], d2[i]));
    }

    for (auto [u, v] : edges) {
        ans = min(ans, 2 * max(d1[u], d2[v]) + 1);
        ans = min(ans, 2 * max(d1[v], d2[u]) + 1);
    }

    cout << ans << '\n';
    return 0;
}

• 서브태스크 1: 22 / 22
• 서브태스크 2: 10 / 10
• 서브태스크 3: 31 / 31
• 서브태스크 4: 37 / 37