Submission #1247433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247433		Anphat	Airplane (NOI23_airplane)	C++20	0 / 100	1099 ms	135728 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 = 2e3 + 10;

int n, m, a[N], mx;
priority_queue <tp, vector <tp>, greater <tp>> pq;
vector <int> graph[N];
unordered_map <int, ll> f[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);
    }

    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].count(i)) f[v][i] = 1e18;
                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].count(i + 1)) f[v][i + 1] = 1e18;
                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].count(i - 1)) f[v][i - 1] = 1e18;
                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 < a[v]) {
                if (!f[v].count(a[v])) f[v][a[v]] = 1e18;
                if (f[v][a[v]] > f[u][i] + a[v] - i) {
                    f[v][a[v]] = f[u][i] + a[v] - i;
                    pq.push({f[v][a[v]], v, a[v]});
                }
            }
        }

        if (i < mx) {
            if (!f[u].count(i + 1)) f[u][i + 1] = 1e18;
            if (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) {
            if (!f[u].count(i - 1)) f[u][i - 1] = 1e18;
            if (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: 0 / 10
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37