← 返回题目列表

AtCoder · pakencamp_2024_day1_l

L. 帕肯王国的出租车

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

配点 : 500 点

問題文

在帕肯王国 N 镇 1, 2, \ldots, N 和不同 2 双向连接两个城镇 M 道路 有 1, 2, \ldots, M 。路 i (1 \leq i \leq M) 是一个城镇 A_i 和镇 B_i 双向连接, 2 没有两条不同的道路连接同一组城镇。从任何一个城镇到任何一个城镇 0 您可以沿着多条道路行驶,但不能仅使用道路从一个城镇行驶到另一个城镇。

嗯,今年PA训练营的季节又到了。公园训练营就在城里 由于活动将在 1 举行,因此来自所有城镇的参与者将 转至 1 。由于携带行李出行比较困难,参与者决定乘坐出租车游览城镇。

在帕肯王国 N 出租车公司 1, 2, \ldots, N 并且每个公司都有以下规则。

  • 的士公司 i 镇上的出租车 您只能从 i 出发。
  • 的士公司 i 的出租车费用与行驶距离无关。 C_i 。
  • 的士公司 i 出租车最多有 R_i 只能使用真实道路。

您可以乘坐多辆出租车,但不得使用出租车以外的任何方式游览城镇。

对于参与者来说,往返每个城镇的交通只能使用出租车。 求前往 1 所需的最低总票价。请注意,根据此限制,所有城镇只能乘坐出租车到达。 我们可以证明我们可以移动到 1 。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
  • (A_i, B_i) \neq (A_j, B_j) (1 \leq i < j \leq M)
  • 从任何城镇到任何城镇 0 可以穿越多条道路 输出
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq R_i \leq 10 (1 \leq i \leq N)
  • 所有输入均为整数 如果有办法做到

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M
C_1 C_2 \ldots C_N
R_1 R_2 \ldots R_N

出力

N 行。 i 行目 (1 \leq i \leq N) 有一个城镇 i 卡拉町 仅在 1 中打印乘坐出租车所需的最低总车费。


入力例 1

5 5
1 2
2 3
3 4
4 5
2 5
100 300 500 200 100
1 2 1 3 1

出力例 1

0
300
700
200
300

帕肯王国如下。

例如,城镇 您可以按如下方式移至 5 卡拉町 仅在 1 。 出租车公司

  1. 町 5 乘坐 5 出租车到镇上 移至 4 。
  2. 町 4 乘坐 4 出租车到镇上 移至 1 。

此时需要的总车费为 100+200=300 。总票价为 没有小于 300 的移动方法,因此 300 。 无论您如何从