← 返回题目列表

AtCoder · abc422_f

I. 吃和骑

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

分数: 500 点

问题陈述

有一个连通无向图 N 顶点和 M 边缘。 顶点编号为顶点 1, 顶点 2,\ldots, 顶点 N,以及 i第边缘 (1\le i\le M) 连接顶点 u _ i 和 v _ i.

对于 i=1,2,\ldots,N,解决以下问题:

最初,高桥的体重是 0.

他开车去拜访顶点 1 并向顶点移动 i。 当他访问顶点时 v\ (1\le v\le N),他的体重增加了 W _ v.

他乘坐的汽车可以沿着边缘移动。 当他穿过边缘时,让 X 是他当时的体重,车耗 X 燃料。

求他到达顶点所消耗的最少燃料量 i.

约束

  • 1\le N\le5000
  • 1\le M\le5000
  • 1\le W _ i\le10 ^ 9\ (1\le i\le N)
  • 1\le u _ i\le v _ i\le N\ (1\le i\le M)
  • 给定的图形已连接。
  • 所有输入值均为整数。

输入

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

N M
W _ 1 W _ 2 \ldots W _ N
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ M v _ M

输出

输出超过 N 行。 上 i第行 (1\le i\le N),输出高桥到达顶点所需的燃料量 i.


示例输入 1

5 6
3 1 4 1 5
1 2
1 3
2 3
2 4
3 5
4 5

示例输出 1

0
3
3
7
10

给出的图表如下:

例如,高桥可以到达顶点 5 通过访问顶点 1 然后执行如下操作:

  • 他访问顶点 1。他的体重增加了 3,成为 3.
  • 他消耗 3 移动到顶点的燃料 3。他的体重增加了 4,成为 7.
  • 他消耗 7 移动到顶点的燃料 5。他的体重增加了 5,成为 12.

通过这种方式,他可以到达顶点 5 通过消费 10 燃料。 不可能将油耗降低到 9 或更少,因此输出 10 上 5第行。


示例输入 2

5 4
1000000000 1000000000 1000000000 1000000000 1000000000
1 2
2 3
3 4
4 5

示例输出 2

0
1000000000
3000000000
6000000000
10000000000

请注意,答案可能会超过 2 ^ {32}.


示例输入 3

10 20
74931 58277 33783 91022 53003 11085 65924 63548 78622 77307
1 8
3 6
5 10
4 6
1 3
1 7
2 6
7 10
8 9
3 4
4 4
4 6
6 6
5 10
1 7
4 5
1 2
3 7
2 3
5 8

示例输出 3

0
74931
74931
183645
213410
183645
74931
74931
213410
215786