Submission #69126808

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ll = long long;
#define fs first 
#define sc second
#define sz(x) (x).size()
#define mkp make_pair
#define pb push_back
using pll = pair<ll,ll>;
#pragma GCC optimize("Ofast")

int seed = 114514;
int n, m, cnt[5100] = {0}, W[5100];
ll ans[5100], www[5100];
vector<ll> e[5100];
set<ll> st[5100];

void solve() {
    cin >> n >> m;
    for (int i =1; i <= n; i++) cin >> W[i];
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    memset(ans, 63, sizeof(ans));
    memset(www, 63, sizeof(www));
    ans[1] = 0;
    priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq;
    pq.push({0,{0,1}});
    while (pq.size()) {
        auto [dis, p] = pq.top(); pq.pop();
        auto [w, id ] = p;
        if (cnt[id] > 5001) continue;
        cnt[id]++;
        if (w >= www[id]) continue;
        www[id] = min(www[id], w);
        ans[id] = min(ans[id], dis);
        for (int j : e[id]) {
            ll nw = w + W[id];
            ll ndis = dis + nw;
            if (cnt[j] <= 5001 and nw<=www[j]) {
                pq.push(mkp(ndis, mkp(nw, j)));
            } 
        }
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    solve();
}

Submission Info

Judge Result