分数: 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 本身确实是间接朋友,但并不属于异国,所以不存在属于异国的受欢迎的人。