提出 #55605212

---

ソースコード 拡げる

// {{{
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#define debug(x...)
#define debug_arr(x...)
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
// }}}

const int N = 2e5 + 10;
int head[N], e;
struct E
{
    LL w;
    int v, next;
} edge[N << 2];

void addedge(int u, int v, LL w)
{
    edge[e].w = w;
    edge[e].v = v, edge[e].next = head[u];
    head[u] = e++;
}

LL a[N];

int pre[N];
LL dis[N];
using pli = pair<LL, int>;
priority_queue<pli, vector<pli>, greater<pli> > q;
void dijkstra(int st)
{
    clr(dis, 0x3f), clr(pre, -1);
    while (!q.empty()) q.pop();

    q.push({dis[st] = a[st], st});
    while (!q.empty())
    {
        auto [du, u] = q.top();
        q.pop();
        // if (u == ed) break;
        if (du != dis[u]) continue;

        for (int i = head[u]; ~i; i = edge[i].next)
        {
            int v = edge[i].v;
            LL val = edge[i].w;
            if (dis[u] + val + a[v] < dis[v])
            {
                dis[v] = dis[u] + val + a[v];
                pre[v] = u;
                q.push({dis[v], v});
            }
        }
    }
}

int n, m;
int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif
    cin.tie(0)->sync_with_stdio(0);

    while (cin >> n >> m)
    {
        clr(head, -1), e = 0;
        for (int i = 1; i <= n; ++i) cin >> a[i];

        for (int i = 1; i <= m; ++i)
        {
            int u, v;
            LL w;
            cin >> u >> v >> w;
            addedge(u, v, w);
            addedge(v, u, w);
        }
        dijkstra(1);
        for (int i = 2; i <= n; i++)
        {
            cout << dis[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

提出情報

ジャッジ結果