Submission #55524036

---

Source Code Expand

#ifndef loc
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif
#include <bits/stdc++.h>
#define fo(i,n) for(long long i = 0; i < n; i++)
#define foa(i,k,n) for(long long i = k; i < n; i++)
#define fob(i,k,n) for(long long i = k; i >= n; i--)
#define pb push_back
#define F first
#define S second
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sortuniq(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
#define uniq(v) {v.erase(unique(v.begin(), v.end()), v.end());}
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
using namespace std;  using ld = long double; using ll = long long; using vi = vector<int>; using vvi = vector<vi>; using vll = vector<ll>; using vvll = vector<vll>; using vb = vector<bool>; using vvb = vector<vb>; using pii = pair<int, int>; using pll = pair<ll, ll>; using vpii = vector<pii>; using vpll = vector<pll>; using arl2 = array<ll, 2>; using arl3 = array<ll, 3>; template <typename T> void ckmin(T &a, const T &b) { a = min(a, b); } template <typename T> void ckmax(T &a, const T &b) { a = max(a, b); } namespace __input {template <class T1, class T2> void re(pair<T1, T2> &p);template <class T> void re(vector<T> &a);template <class T, size_t SZ> void re(array<T, SZ> &a);template <class T> void re(T &x) { cin >> x; }void re(double &x) { string t; re(t); x = stod(t); }template <class Arg, class... Args> void re(Arg &first, Args &...rest) { re(first); re(rest...); }template <class T1, class T2> void re(pair<T1, T2> &p) { re(p.f, p.s); }template <class T> void re(vector<T> &a) { for (int i = 0; i < sz(a); i++) re(a[i]); }template <class T, size_t SZ> void re(array<T, SZ> &a) { for (int i = 0; i < SZ; i++) re(a[i]); }} using namespace __input;
namespace __output {template <typename T> struct is_outputtable { template <typename C> static constexpr decltype(declval<ostream &>() << declval<const C &>(), bool()) test(int) { return true; } template <typename C> static constexpr bool test(...) { return false; } static constexpr bool value = test<T>(int()); };template <class T, typename V = decltype(declval<const T &>().begin()), typename S = typename enable_if<!is_outputtable<T>::value, bool>::type> void pr(const T &x);template <class T, typename V = decltype(declval<ostream &>() << declval<const T &>())> void pr(const T &x) { cout << x; }template <class T1, class T2> void pr(const pair<T1, T2> &x);template <class Arg, class... Args> void pr(const Arg &first, const Args &...rest) { pr(first); pr(rest...); }template <class T, bool pretty = true> void prContain(const T &x) { if (pretty) pr("{"); bool fst = 1; for (const auto &a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0; if (pretty) pr("}"); }template <class T> void pc(const T &x) { prContain<T, false>(x); pr("\n"); }template <class T1, class T2> void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }template <class T, typename V, typename S> void pr(const T &x) { prContain(x); }void ps() { pr("\n"); }template <class Arg> void ps(const Arg &first) { pr(first); ps(); }template <class Arg, class... Args> void ps(const Arg &first, const Args &...rest) { pr(first, " "); ps(rest...); }} using namespace __output;
#define __pn(x) pr(#x, " = ")
#define pd(...) __pn((__VA_ARGS__)), ps(__VA_ARGS__), cout << flush
#define noo {ps("NO");return;}
#define yess {ps("YES");return;}
#define Multitests 0 //#define int long long

template<typename T_weight>
struct Dijkstra {
    const T_weight W_INF = numeric_limits<T_weight>::max() / 2;

    struct edge {
        int node = -1;
        T_weight weight = 0;

        edge() {}

        edge(int _node, T_weight _weight) : node(_node), weight(_weight) {}
    };

    struct state {
        T_weight dist;
        int node;

        state() {}

        state(T_weight _dist, int _node) : dist(_dist), node(_node) {}

        bool operator<(const state &other) const {
            return dist > other.dist;
        }
    };

    int n;
    vector<vector<edge>> adj;
    vector<T_weight> dist;
    vector<int> parent;

    Dijkstra(int _n = 0) {
        init(_n);
    }

    void init(int _n) {
        n = _n;
        adj.assign(n, {});
    }

    void add_directional_edge(int a, int b, T_weight weight) {
        adj[a].emplace_back(b, weight);
    }

    void add_bidirectional_edge(int a, int b, T_weight weight) {
        add_directional_edge(a, b, weight);
        add_directional_edge(b, a, weight);
    }

    void dijkstra_check(priority_queue<state> &pq, int node, int from, T_weight new_dist) {
        if (new_dist < dist[node]) {
            dist[node] = new_dist;
            parent[node] = from;
            pq.emplace(new_dist, node);
        }
    }

    void dijkstra(const vector<int> &source) {
        if (n == 0) return;
        dist.assign(n, W_INF);
        parent.assign(n, -1);
        priority_queue<state> pq;

        for (int src : source)
            dijkstra_check(pq, src, -1, 0);

        while (!pq.empty()) {
            state top = pq.top();
            pq.pop();

            if (top.dist > dist[top.node])
                continue;

            for (edge &e : adj[top.node])
                dijkstra_check(pq, e.node, top.node, top.dist + e.weight);
        }
    }
};


void solve(){
	ll n, m; cin >> n >> m;
	Dijkstra<int64_t> d(n * 2);
	fo(i, n){
		ll w; cin >> w;
		d.add_bidirectional_edge(i * 2, i * 2 + 1, w);
	}
	fo(i, m){
		ll u, v, w; cin >> u >> v >> w;
		u--, v--;
		d.add_directional_edge(u * 2 + 1, v * 2, w);
		d.add_directional_edge(v * 2 + 1, u * 2, w);
	}
	d.dijkstra({0});
	foa(i, 1, n){
		cout << d.dist[i * 2 + 1] << " ";
	}
	cout << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout << setprecision(15);
	if(Multitests){
		int t; cin >> t;  fo(i, t) solve();
	}else solve();
    return 0;
}

Submission Info

Judge Result