제출 #1275326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275326		sh1ft	Airplane (NOI23_airplane)	C++17	10 / 100	1114 ms	465716 KiB

Main

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 2e5+5;

int n, m;
ll a[mxN], ans = LLONG_MAX;
vector <int> adj[mxN];
unordered_map <ll, ll> dis[mxN], vis[mxN];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0, u, v; i < m; i++) cin >> u >> v, adj[u].emplace_back(v), adj[v].emplace_back(u);
    priority_queue <tuple <ll, ll, ll, int>> q;
    q.emplace(0, 0, 0, 1);
    vis[1][0] = 1;
    while (!q.empty()) {
        auto [t, L, R, u] = q.top(); q.pop();
        if (u == n) { ans = min(ans, (-t) + R); continue; }
        for (auto v : adj[u]) {
            ll w = 1, l = L+1, r = R;
            if (a[v] > l) w += a[v] - l, l = a[v];
            r--;
            r = max(r, a[v]);
            if (!vis[v][r] || dis[v][r] > -t + w) q.emplace(-(dis[v][r] = -t + w), l, r, v), vis[v][r] = 1;
        }
    }
    cout << ans << '\n';
}

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