← 返回题目列表

Codeforces · 2041/N

N. 铁路建设

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

特拉斯基国家位于崎岖的山区,地质条件引发了一系列问题。具有挑战性的地形将该国不同的州分开,导致州际通勤极其不便,更重要的是缺乏中央政府的控制。除此之外,犯罪率逐年上升,严重扰乱了无辜公民的日常生活。

最近的抗议活动终于揭示了情况,因为新当选的总统宣布了一项雄心勃勃的项目来解决这些问题。她的计划由两个主要部分组成。首先是建设州际高速铁路,以促进全国各地更好的联系和团结。由于各州大多彼此独立运行,要在 $$$u$$$ 州和 $$$v$$$ 州之间修建铁路,政府必须支付 $$$a_u + a_v$$$ 美元的费用,其中 $$$a_u$$$ 美元给州 $$$u$$$,$$$a_v$$$ 美元给州 $$$v$$$。该铁路是双向运营的,这意味着一旦建成,来自 $$$u$$$ 州的人们现在可以前往 $$$v$$$ 州,反之亦然。几乎任何两个州之间都可以修建铁路,但有一些特定的州除外,因为它们之间的地形非常危险,以至于在两个州之间修建直达铁路是不可能的。

该项目的第二个组成部分是建立一个集中监狱,管理全国所有的罪犯。鉴于估计囚犯人数众多,总统决定选择其中一个州建造中央监狱,并切断该州与全国其他地区的联系。

示例输入 1 的说明。(a) 在各州之间修建直达铁路的成本。 (b) 考虑在#3 州建造中央监狱。必须修建所有不涉及第 3 州的直达铁路,总成本为 $$$3+3+2=8$$$ 美元。

鉴于上述情况,总统希望寻找在各州之间建设铁路的最低成本计划,以便:

- 有中央监狱的州不应有任何铁路将其连接到任何其他州,并且
- 所有其他州都应该连接起来,即人们应该能够从一个这样的州前往另一个州,可能需要乘坐多趟火车。

您在负责施工总体规划的团队工作。几个小时后就要与总统会面,届时您必须向她介绍不同建设计划的成本。请计算每个州$$$u$$$在$$$u$$$为中央监狱所在地时,满足上述条件的州之间修建铁路的最低成本计划。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$,即 Truckski 中的州数以及铁路建设不可行的对数。下一行包含$$$n$$$整数$$$a_1,\ldots,a_n$$$,政府需要向第$$$i$$$个州支付的建设费。然后是 $$$m$$$ 行。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ 意味着不可能在 $$$u_i$$$ 州和 $$$v_i$$$ 州之间修建(直接)铁路。

- $$$2\leq n\leq 10^5$$$
- $$$0\leq m\leq 10^5$$$
- $$$1\leq a_i\leq 10^9$$$
- $$$1\leq u_i<v_i\leq n$$$
- 对于所有$$$i\neq j,(u_i, v_i)\neq (u_j, v_j)$$$。

输出

在一行中输出 $$$n$$$ 个整数。第 $$$i$$$ 个整数是当第 $$$i$$$ 个州是建造监狱时的最低建设成本。如果无法找到可行的铁路建设,则输出-1。

示例

输入 #1

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

输出 #1

7 6 8 7 7

输入 #2

3 2
1 2 3
1 2
2 3

输出 #2

-1 4 -1