AT_abc245_g [ABC245G] Foreign Friends

题目描述

有 $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$ 与一个属于不同国家的“人气者”间接成为朋友？如果可以，请求出达成这一目标所需的最小总费用。这里，若存在某个非负整数 $n$ 和一列人 $(u_0, u_1, \ldots, u_n)$，满足 $u_0=s$，$u_n=t$，且对于所有 $0\leq i < n$，人 $u_i$ 和人 $u_{i+1}$ 是朋友，则称人 $s$ 和人 $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$ 为让人 $i$ 与属于不同国家的“人气者”间接成为朋友所需的最小费用。如果无法达成，则 $X_i=-1$。请将 $X_1,X_2,\ldots,X_N$ 以空格分隔输出在一行。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #2

3 1 3 1
1 2 3
1
1 2 1000000000

输出 #2

-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 < B_2 < \cdots < B_L\leq N$
• $1\leq C_i\leq 10^9$
• $1\leq U_i < V_i\leq N$
• 若 $i\neq j$，则 $(U_i, V_i)\neq (U_j, V_j)$
• 所有输入均为整数。

样例解释 1

人 $1$、人 $2$、人 $3$、人 $4$ 分别属于国家 $1$、国家 $1$、国家 $2$、国家 $2$，人气者为人 $2$、人 $3$ 共 $2$ 人。此时：

• 对于人 $1$，属于不同国家的人气者只有人 $3$。让人 $1$ 与人 $3$ 间接成为朋友的最小费用为 $15+30=45$（即先支付 $15$ 让人 $1$ 与人 $2$ 成为朋友，再支付 $30$ 让人 $2$ 与人 $3$ 成为朋友）。
• 对于人 $2$，属于不同国家的人气者只有人 $3$。直接支付 $30$ 让人 $2$ 与人 $3$ 成为朋友，费用最小。
• 对于人 $3$，属于不同国家的人气者只有人 $2$。直接支付 $30$ 让人 $2$ 与人 $3$ 成为朋友，费用最小。
• 对于人 $4$，属于不同国家的人气者只有人 $2$。让人 $4$ 与人 $2$ 间接成为朋友的最小费用为 $10+15=25$（即先支付 $10$ 让人 $1$ 与人 $4$ 成为朋友，再支付 $15$ 让人 $1$ 与人 $2$ 成为朋友）。

样例解释 2

对于人 $1$，虽然自己可以算作间接朋友，但由于没有属于不同国家的人气者，故不存在满足条件的对象。请注意“属于不同国家的人气者”的条件。

由 ChatGPT 4.1 翻译