Submission #69151124

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <queue>
#include <ranges>
#include <tuple>
#include <utility>
#include <vector>

template <typename T>
using g_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

int main()
{
    using namespace std;
    int n, m;
    cin >> n >> m;
    using lint = long long;
    vector<lint> ws(n);
    for (auto &e : ws) cin >> e;
    vector g(n, vector<int>());
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    const lint oo = 1e18;
    vector dist(n, vector(n + 10, oo));
    for (int mu = 0; mu < n + 10; mu++) {
        dist[0][mu] = 0;
    }
    for (int mu = n + 10; mu-- > 1;) {
        for (int v = 0; v < n; ++v) {
            lint nd = dist[v][mu] + mu * ws[v];
            for (int nv : g[v]) {
                dist[nv][mu - 1] = min(dist[nv][mu - 1], nd);
            }
        }
    }
    for (int v = 0; v < n; ++v) {
        lint ans = ranges::min(dist[v]);
        cout << ans << '\n';
    }
}

Submission Info

Judge Result