Foreign Friends

题目描述

有 $N$ 个人和 $K$ 个国家，分别标记为 Person $1$, Person $2$, $\ldots$, Person $N$ 和 Nation $1$, Nation $2$, $\ldots$, Nation $K$。
每个人恰好属于一个国家：Person $i$ 属于 Nation $A_i$。 另外，他们中有 $L$ 个受欢迎的人：Person $B_1$, Person $B_2$, $\ldots$, Person $B_L$ 是受欢迎的人。 最初，$N$ 个人之间没有任何朋友关系。 对于 $M$ 对人，Takahashi（一位神）可以通过付出一定代价让他们成为朋友：对于每个 $1\leq i\leq M$，他可以付出代价 $C_i$ 使 Person $U_i$ 和 Person $V_i$ 成为朋友。 现在，对于每个 $1\leq i\leq N$，解答以下问题。

Takahashi 是否可以使 Person $i$ 成为属于不同于 Person $i$ 的国家的受欢迎者的间接朋友？ 如果可以的话，求使其成立所需的最小总代价。 这里，当存在非负整数 $n$ 和一列人 $(u_0, u_1, \ldots, u_n)$ 使得 $u_0=s$, $u_n=t$, 且对于每个 $0\leq i < n$，Person $u_i$ 和 Person $u_{i+1}$ 是朋友时，称 Person $s$ 是 Person $t$ 的间接朋友。

输入格式

输入由标准输入按以下格式给出： $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$ 定义如下：若不可能使 Person $i$ 成为属于不同于 Person $i$ 的国家的受欢迎者的间接朋友，则 $X_i$ 为 $-1$；否则，$X_i$ 为所需的最小总代价。 在一行中输出 $X_1, X_2, \ldots, X_N$，中间用空格分隔。

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

45 30 30 25

3 1 3 1
1 2 3
1
1 2 1000000000

-1 1000000000 -1

提示

$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&lt;B_2&lt;\cdots&lt;B_L\leq N $1\leq C_i\leq 10^9$ 1\leq U_i&lt;V_i\leq N $(U_i, V_i)\neq (U_j,V_j)$ if $i \neq j$. 输入中的所有数值均为整数。Person $1$, $2$, $3$, $4$ 分别属于 Nation $1$, $1$, $2$, $2$，并且有两位受欢迎的人：Person $2$ 和 $3$。在这里，

对于 Person $1$，唯一属于不同国家的受欢迎者是 Person $3$。要以最小代价使他们成为间接朋友，应付出 $15$ 使 Person $1$ 和 $2$ 成为朋友，和付出 $30$ 使 Person $2$ 和 $3$ 成为朋友，总计 $15+30=45$。 对于 Person $2$，唯一属于不同国家的受欢迎者是 Person $3$。最小代价通过付出 $30$ 使 Person $2$ 和 $3$ 成为朋友实现。 对于 Person $3$，唯一属于不同国家的受欢迎者是 Person $2$。最小代价通过付出 $30$ 使 Person $2$ 和 $3$ 成为朋友实现。 对于 Person $4$，唯一属于不同国家的受欢迎者是 Person $2$。要以最小代价使他们成为间接朋友，应付出 $15$ 使 Person $1$ 和 $2$ 成为朋友，和付出 $10$ 使 Person $1$ 和 $4$ 成为朋友，总计 $15+10=25$。
注意，对于 Person $1$，Person $1$ 本身确实是一个间接朋友，但它不属于不同的国家，所以不存在属于不同国家的受欢迎者。

标签: AtCoder|abc245G

来源

AtCoder|abc245G