제출 #1272797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272797		ortsac	Airplane (NOI23_airplane)	C++20	100 / 100	391 ms	27116 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

const int INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 10;
vector<int> adj[MAXN];
int v[MAXN];
int n, m;

vector<int> calc(int s) {
    vector<int> r(n + 1, INF);
    vector<int> ok(n + 1);
    r[s] = 0;
    priority_queue<pii> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().se;
        pq.pop();
        if (ok[u]) continue;
        ok[u] = 1;
        for (auto to : adj[u]) {
            int newD = max(v[to], r[u] + 1);
            if (r[to] > newD) {
                r[to] = newD;
                pq.push({-r[to], to});
            }
        }
    }
    return r;
}

int32_t main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<int> r1 = calc(1), rn = calc(n);
    int ans = INF;
    for (int i = 1; i <= n; i++) {
        for (auto u : adj[i]) ans = min(ans, r1[i] + rn[u] + max(1LL, abs(r1[i] - rn[u])));
    }
    cout << ans << "\n";
}

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