AT_abc362_d.[ABC362D] Shortest Path 3

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有 $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
```
3 3
1 2 3
1 2 1
1 3 6
2 3 2
```
输出#1
```
4 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

说明/提示

限制条件

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页