AT_abc362_d [ABC362D] 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$ 的答案，用空格分隔，输出一行。

输入输出样例 #1

输入 #1

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

输出 #1

4 9

输入输出样例 #2

输入 #2

2 1
0 1
1 2 3

输出 #2

4

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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$
• 若 $i \neq j$，则 $(U_i,V_i) \neq (U_j,V_j)$
• 图是连通的
• $0 \leq A_i \leq 10^9$
• $0 \leq B_j \leq 10^9$
• 所有输入均为整数

样例解释 1

考虑从顶点 $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$。

样例解释 3

请注意，答案可能超出 32 位整数范围。

由 ChatGPT 4.1 翻译