Submission #1102454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102454		ShadowShark	Airplane (NOI23_airplane)	C++17	100 / 100	247 ms	21508 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>

const int maxN = 2e5 + 5, inf = 1e9;
int n, m, a[maxN]; pii dis[3][maxN];
vector<int> adj[maxN];

void dijkstra(int type, int st) {
    priority_queue<pair<pii, int>, vector<pair<pii, int>>, greater<pair<pii, int>>> pq;
    dis[type][st] = {0, 0};
    pq.push({dis[type][st], st});

    while (pq.size() > 0) {
        int len = pq.top().first.first, height = pq.top().first.second, u = pq.top().second; pq.pop();

        if (dis[type][u].first != len || dis[type][u].second != height) continue;

        for (auto v: adj[u]) {
            pair<int, int> nw = {len + max(1, a[v] - len), max(height, a[v])};

            if (dis[type][v] > nw) {
                dis[type][v] = nw;
                pq.push({nw, v});
            }
        }
    }
}

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        dis[1][i] = dis[2][i] = {inf, 0};
    }

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dijkstra(1, 1);
    dijkstra(2, n);

    int ans = inf;
    for (int i = 1; i <= n; i++)
        if (dis[1][i].second == a[i] && dis[2][i].second == a[i])
            ans = min(ans, dis[1][i].first + dis[2][i].first);

    cout << ans;
    return 0;
}

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