Shortest Path 3

题目描述

你被给定一个包含 $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$ 的路径的最小权重。

输入格式

输入从标准输入按以下格式给出： $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$ 的答案，答案之间用空格分隔。

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

4 9

2 1
0 1
1 2 3

4

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

2832044198 2824130042 4696218483 2805069468

提示

$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$ 所有输入值均为整数。考虑从顶点 $1$ 到顶点 $2$ 的路径。 路径 $1 \to 2$ 的权重是 $A_1 + B_1 + A_2 = 1 + 1 + 2 = 4$，而路径 $1 \to 3 \to 2$ 的权重是 $A_1 + B_2 + A_3 + B_3 + A_2 = 1 + 6 + 3 + 2 + 2 = 14$。最小权重是 $4$。 考虑从顶点 $1$ 到顶点 $3$ 的路径。 路径 $1 \to 3$ 的权重是 $A_1 + B_2 + A_3 = 1 + 6 + 3 = 10$，而路径 $1 \to 2 \to 3$ 的权重是 $A_1 + B_1 + A_2 + B_3 + A_3 = 1 + 1 + 2 + 2 + 3 = 9$。最小权重是 $9$。
注意答案可能无法放入 32 位整数。

标签: AtCoder|abc362D

来源

AtCoder|abc362D