← 返回题目列表

AtCoder · abc362_d

G. 最短路径3

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

给你一个简单的连通无向图 N 顶点和 M 边缘。每个顶点 i\,(1\leq i \leq N) 有一个重量 A_i。每条边 j\,(1\leq j \leq M) 连接顶点 U_j 和 V_j 双向且具有权重 B_j.

该图中路径的权重定义为路径上出现的顶点和边的权重之和。

对于每个 i=2,3,\dots,N,解决以下问题:

  • 查找从顶点开始的路径的最小权重 1 到顶点 i.

约束

  • 2 \leq N \leq 2 \times 10^5
  • N-1 \leq M \leq 2 \times 10^5
  • 1 \leq U_j < V_j \leq N
  • (U_i, V_i) \neq (U_j, V_j) if i \neq j.
  • 该图已连接。
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_j \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \dots A_N
U_1 V_1 B_1
U_2 V_2 B_2
\vdots
U_M V_M B_M

输出

打印以下问题的答案 i=2,3,\dots,N 位于一行中,以空格分隔。


示例输入 1

3 3
1 2 3
1 2 1
1 3 6
2 3 2

示例输出 1

4 9

考虑从顶点开始的路径 1 到顶点 2。 路径的权重 1 \to 2 is A_1 + B_1 + A_2 = 1 + 1 + 2 = 4,以及路径的权重 1 \to 3 \to 2 is A_1 + B_2 + A_3 + B_3 + A_2 = 1 + 6 + 3 + 2 + 2 = 14。最小重量为 4.

考虑从顶点开始的路径 1 到顶点 3。 路径的权重 1 \to 3 is A_1 + B_2 + A_3 = 1 + 6 + 3 = 10,以及路径的权重 1 \to 2 \to 3 is A_1 + B_1 + A_2 + B_3 + A_3 = 1 + 1 + 2 + 2 + 3 = 9。最小重量为 9.


示例输入 2

2 1
0 1
1 2 3

示例输出 2

4

示例输入 3

5 8
928448202 994752369 906965437 942744902 907560126
2 5 975090662
1 2 908843627
1 5 969061140
3 4 964249326
2 3 957690728
2 4 942986477
4 5 948404113
1 3 988716403

示例输出 3

2832044198 2824130042 4696218483 2805069468

请注意,答案可能不适合 32 位整数。