← 返回题目列表

AtCoder · abc245_g

G. 外国友人

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

分数: 600 点

问题陈述

有 N 人和 K 国家,标记为“人” 1, 人 2, \ldots, 人 N 和国家 1,国家 2, \ldots,国家 K。
每个人都属于一个国家:人 i 属于国家 A_i。 此外,还有 L 其中受欢迎的人: 人 B_1, 人 B_2, \ldots, 人 B_L 很受欢迎。 最初,没有两个 N 人们都是朋友。

对于 M 成对的人,高桥神,可以通过支付一定的成本使他们成为朋友:对于每个人 1\leq i\leq M,他可以支付以下费用 C_i 使人 U_i 和人 V_i 朋友们。

现在,对于每个 1\leq i\leq N,解决以下问题。

高桥能造人吗 i 属于与该人不同国家的受欢迎人物的间接朋友 i? 如果他能做到,请找出所需的最小总成本。 在这里,人 s 据说是 Person 的间接朋友 t 当存在非负整数时 n 和一系列人 (u_0, u_1, \ldots, u_n) 这样 u_0=s, u_n=t和人 u_i 和人 u_{i+1} 都是朋友 0\leq i < n.

约束

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq 10^5
  • 1 \leq L \leq N
  • 1 \leq A_i \leq K
  • 1 \leq B_1<B_2<\cdots<B_L\leq N
  • 1\leq C_i\leq 10^9
  • 1\leq U_i<V_i\leq N
  • (U_i, V_i)\neq (U_j,V_j) if i \neq j.
  • 输入中的所有值都是整数。 您选择的

输入

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

N M K L
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_L
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M

输出

让 X_i 定义如下: X_i is -1 如果不可能使人 i 属于与该人不同国家的受欢迎人物的间接朋友 i;否则, X_i 是执行此操作所需的最低总成本。 打印 X_1, X_2, \ldots, X_N 位于一行,中间有空格。


示例输入 1

4 4 2 2
1 1 2 2
2 3
1 2 15
2 3 30
3 4 40
1 4 10

示例输出 1

45 30 30 25

人 1, 2, 3, 4 属于国家 1, 1, 2, 2分别有两个热门人物: 2 和 3。在这里,

  • 对于人 1,属于不同国家的唯一受欢迎的人是 Person 3。为了以最小的成本让他们成为间接的朋友,我们应该付出以下的成本: 15 使人 1 和 2 好友并付款 30 使人 2 和 3 朋友们,总共 15+30=45.
  • 对于人 2,属于不同国家的唯一受欢迎的人是 Person 3。通过使 Person 实现最小成本 2 和 3 好友通过支付 30.
  • 对于人 3,属于不同国家的唯一受欢迎的人是 Person 2。通过使 Person 实现最小成本 2 和 3 好友通过支付 30.
  • 对于人 4,属于不同国家的唯一受欢迎的人是 Person 2。为了以最小的成本让他们成为间接的朋友,我们应该付出以下的成本: 15 使人 1 和 2 好友并付款 10 使人 1 和 4 朋友们,总共 15+10=25.

示例输入 2

3 1 3 1
1 2 3
1
1 2 1000000000

示例输出 2

-1 1000000000 -1

请注意,对于 Person 1, 人 1 本身确实是间接朋友,但并不属于异国,所以不存在属于异国的受欢迎的人。