제출 #1247432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247432		Anphat	Airplane (NOI23_airplane)	C++20	0 / 100	0 ms	324 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define tp tuple<ll, int, int>
const int N = 2e3 + 10;
const ll INF = 1e18;

int n, m;
int a[N], mx;
vector<int> graph[N];
vector<int> all_heights;
unordered_map<int, int> compress; // độ cao thực -> index rời rạc
ll f[N][6010]; // f[u][height_index]

// Rời rạc hóa
void prepare_compression() {
    sort(all_heights.begin(), all_heights.end());
    all_heights.erase(unique(all_heights.begin(), all_heights.end()), all_heights.end());

    for (int i = 0; i < all_heights.size(); ++i)
        compress[all_heights[i]] = i;
}

void solve() {
    cin >> n >> m;
    mx = 0;
    all_heights.clear();

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);

        all_heights.push_back(a[i]);
        if (a[i] > 0) all_heights.push_back(a[i] - 1);
        if (a[i] < 1e8) all_heights.push_back(a[i] + 1);
    }

    all_heights.push_back(0);
    all_heights.push_back(mx);

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

    prepare_compression();
    int H = all_heights.size();

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < H; ++j)
            f[i][j] = INF;

    int h0 = compress[0];
    f[1][h0] = 0;

    priority_queue<tp, vector<tp>, greater<tp>> pq;
    pq.push({0, 1, h0});

    while (!pq.empty()) {
        auto [w, u, h] = pq.top(); pq.pop();
        if (w > f[u][h]) continue;

        int real_h = all_heights[h];

        // Di chuyển sang đỉnh kề
        for (int v : graph[u]) {
            if (real_h >= a[v]) {
                int nh = compress[real_h];
                if (f[v][nh] > f[u][h] + 1) {
                    f[v][nh] = f[u][h] + 1;
                    pq.push({f[v][nh], v, nh});
                }
            }

            // Tăng độ cao nếu cần
            if (real_h < a[v]) {
                int nh = compress[a[v]];
                ll cost = f[u][h] + a[v] - real_h + 1;
                if (f[v][nh] > cost) {
                    f[v][nh] = cost;
                    pq.push({cost, v, nh});
                }
            }
        }

        // Tăng độ cao
        if (real_h < mx) {
            int nh = compress[real_h + 1];
            if (f[u][nh] > f[u][h] + 1) {
                f[u][nh] = f[u][h] + 1;
                pq.push({f[u][nh], u, nh});
            }
        }

        // Giảm độ cao
        if (real_h > 0 && compress.count(real_h - 1)) {
            int nh = compress[real_h - 1];
            if (f[u][nh] > f[u][h] + 1) {
                f[u][nh] = f[u][h] + 1;
                pq.push({f[u][nh], u, nh});
            }
        }
    }

    cout << f[n][compress[0]] << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    solve();
    return 0;
}

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