题解：AT_abc362_d [ABC362D] Shortest Path 3

1
// Problem: D - Shortest Path 3
2
// Contest: AtCoder - Toyota Programming Contest 2024#7（AtCoder Beginner Contest 362）
3
// URL: https://atcoder.jp/contests/abc362/tasks/abc362_d
4
// Memory Limit: 1024 MB
5
// Time Limit: 2000 ms
6
//
7
// Powered by CP Editor (https://cpeditor.org)
8

9
/*Code by Block_Fish*/
10
#include <bits/stdc++.h>
11

12
#define log printf
13
#define EPS 1e-8
14
#define INF 0x3f3f3f3f3f3f3f3f
15
#define FOR(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
16
#define IOS                      \
17
  ios::sync_with_stdio(false); \
18
  cin.tie(nullptr);            \
19
  cout.tie(nullptr);
20

21
using namespace std;
22

23
typedef __int128 i128;
24
typedef long long ll;
25
typedef pair<ll, ll> PII;
26

27
const ll N = 1e6 + 10;
28
ll m, n, s, x, y, z, a[N], w[N], to[N], idx, dis[N], nxt[N], head[N];
29

30
struct line {
31
  ll u, d;
32
  bool operator<(const line &cmp) const { return d > cmp.d; }
33
};
34
priority_queue<line> q;
35

36
template <typename T>
37

38
inline T read() {
39
  T sum = 0, fl = 1;
40
  char ch = getchar();
41
  for (; !isdigit(ch); ch = getchar())
42
    if (ch == '-') fl = -1;
43
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
44
  return sum * fl;
45
}
46

47
template <typename T>
48

49
inline void write(T x) {
50
  if (x < 0) putchar('-'), write<T>(-x);
51
  static T sta[35];
52
  ll top = 0;
53
  do { sta[top++] = x % 10, x /= 10; } while (x);
54
  while (top) putchar(sta[--top] + 48);
55
}
56

57
inline void init() {
58
  memset(head, -1, sizeof(head));
59
  memset(dis, 0x3f, sizeof(dis));
60
}
61

62
inline void addEdge(ll u, ll v, ll q) {
63
  w[idx] = q;
64
  to[idx] = v;
65
  nxt[idx] = head[u];
66
  head[u] = idx;
67
  idx++;
68
}
69

70
void dijkstra(ll s) {
71
  dis[s] = 0;
72
  q.push({s, 0});
73
  while (!q.empty()) {
74
    line f = q.top();
75
    q.pop();
76
    ll u = f.u;
77
    if (f.d > dis[u]) continue;
78
    for (ll i = head[u]; i != -1; i = nxt[i]) {
79
      ll v = to[i];
80
      if (dis[u] + w[i] + a[v] < dis[v]) {
81
        dis[v] = dis[u] + w[i] + a[v];  // 把要去的点的点权算上
82
        q.push({v, dis[v]});
83
      }
84
    }
85
  }
86
}
87

88
int main() {
89
  init();
90
  n = read<ll>(), m = read<ll>(), s = 1;
91
  FOR(i, 1, n) a[i] = read<ll>();
92
  FOR(i, 1, m) {
93
    x = read<ll>(), y = read<ll>(), z = read<ll>();
94
    addEdge(x, y, z), addEdge(y, x, z);
95
  }
96
  dijkstra(s);
97
  FOR(i, 2, n)
98
  write<ll>(dis[i] + a[1]), putchar(' ');  // 除了起点都有了，所以要加上起点
99
  return 0;
100
}