← Real problems

cco24p1

easygraphdijkstramulti-sourceStatement on DMOJ

CP Lang

9 lineschecks
// cco24p1 Treasure Hunt: from each cave, the best a[u] - dist(v, u) over every cave u. Negated,
// that is a shortest path from every cave at once, cave u starting at -a[u].
let (n, m) = read<(1..=200_000, 0..=200_000)>()
domain V = 1..=n
let a = read<[V]1..=1_000_000_000>()
let g = Graph.undirected(read<[m](u: V, v: V, w: 1..=1_000_000_000)>())
let p = dijkstra(g, from: V.map(v => (v, -a[v])))
for v in V:
    print(-p[v]!)

Accepted C++

91 lines · 36.09 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

void init_io() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
}

template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<>>;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> arr(n);
    for (auto& a : arr) {
        cin >> a;
    }

    vector<pair<int, int>> graph[n];
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }

    vector<long> dist(n, 1e18);
    min_pq<pair<long, int>> pq;
    auto push = [&](int u, long d) -> void {
        if (d >= dist[u]) {
            return;
        }

        dist[u] = d;
        pq.emplace(d, u);
    };

    for (int i = 0; i < n; i++) {
        push(i, -arr[i]);
    }

    while (sz(pq)) {
        auto [d, u] = pq.top();
        pq.pop();

        if (dist[u] != d) {
            continue;
        }

        for (auto& [v, w] : graph[u]) {
            push(v, d + w);
        }
    }

    for (auto& a : dist) {
        cout << -a << endl;
    }
}

int main() {
    init_io();
    solve();
}