提出 #57838602

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <queue>

const long long LINF = 1ull << 60u;

using namespace std;


int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;

    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }

    vector<vector<pair<int, long long>>> graph(N);
    for (int i = 0; i < M; ++i) {
        int U, V;
        cin >> U >> V;
        U--;
        V--;

        if (H[U] >= H[V]) {
            graph[U].emplace_back(V, 0);
            graph[V].emplace_back(U, H[U] - H[V]);
        } else {
            graph[V].emplace_back(U, 0);
            graph[U].emplace_back(V, H[V] - H[U]);
        }
    }

    // dijkstra
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> que;
    que.emplace(0, 0);

    vector<bool> seen(N);
    vector<long long> distance(N, LINF);
    distance[0] = 0;

    while (not que.empty()) {
        const auto [now_dist, u] = que.top();
        que.pop();
        if (seen[u]) {
            continue;
        }
        seen[u] = true;

        for (auto [v, d]: graph[u]) {
            const auto new_dist = now_dist + d;
            if (new_dist < distance[v]) {
                distance[v] = new_dist;
                que.emplace(new_dist, v);
            }
        }
    }

    long long ans = LINF;
    for (int u = 0; u < N; ++u) {
        ans = min(ans, distance[u] - H[0] + H[u]);
    }
    cout << -ans << endl;

    return 0;
}

提出情報

ジャッジ結果