제출 #1247434

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

Main

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

#define ll long long
#define f first
#define s second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define uni(a) sort(all(a)), (a).resize(unique(all(a)) - (a).begin())

typedef tuple <int, int, int> tp;
typedef pair <int, int> ii;

const int N = 4e3 + 10;

int n, m, a[N], f[N][N], mx;
priority_queue <tp, vector <tp>, greater <tp>> pq;
vector <int> graph[N];
ii edge[N];

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

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

    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;
    pq.push({0, 1, 0});

    while (sz(pq)) {
        ll w, u, i; tie(w, u, i) = pq.top(); pq.pop();
        if (w > f[u][i]) continue;

        for (int v : graph[u]) {
            if (i >= a[v]) {
                if (f[v][i] > f[u][i] + 1) {
                    f[v][i] = f[u][i] + 1;
                    pq.push({f[v][i], v, i});
                }
            }

            if (i < mx && i + 1 >= a[v]) {
                if (f[v][i + 1] > f[u][i] + 1) {
                    f[v][i + 1] = f[u][i] + 1;
                    pq.push({f[v][i + 1], v, i + 1});
                }
            }

            if (i > 0 && i - 1 >= a[v]) {
                if (f[v][i - 1] > f[u][i] + 1) {
                    f[v][i - 1] = f[u][i] + 1;
                    pq.push({f[v][i - 1], v, i - 1});
                }
            }
        }

        if (i < mx && f[u][i + 1] > f[u][i] + 1) {
            f[u][i + 1] = f[u][i] + 1;
            pq.push({f[u][i + 1], u, i + 1});
        }

        if (i > 0 && f[u][i - 1] > f[u][i] + 1) {
            f[u][i - 1] = f[u][i] + 1;
            pq.push({f[u][i - 1], u, i - 1});
        }
    }

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

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

    // freopen("airplane.inp", "r", stdin);
    // freopen("airplane.out", "w", stdout);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

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