G - Foreign Friends 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

N 人の人と K 個の国があり、それぞれ 人 1, 人 2, \ldots, 人 N および国 1, 国 2, \ldots, 国 K と番号が付いています。 それぞれの人はちょうど 1 つの国に属しており、人 i は国 A_i に属しています。 また、L 人の人気者がおり、具体的には人 B_1, 人 B_2, \ldots, 人 B_L が人気者です。 最初、N 人のうちどの 2 人も友達ではありません。

神様である高橋君は、M 個の 2 人組のペアについて、コストを支払うことで互いに友達にすることができます。 具体的には 1\leq i\leq M について、コスト C_i を支払うことで人 U_i と人 V_i を互いに友達にすることができます。

ここで、各 1\leq i\leq N について、次の問題を解いてください。

高橋君は、人 i を、人 i の属する国とは異なる国に属する人気者と間接的に友達にすることは可能か？ 可能ならば、それを達成するのに必要なコストの総和の最小値を求めよ。 ただし、人 s と人 t が間接的に友達であるとは、ある非負整数 n と人の列 (u_0, u_1, \ldots , u_n) が存在し, u_0=s, u_n=t かつ 0\leq i < n について、人 u_i と 人 u_{i+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)
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

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 を異なる国に属する人気者と間接的に友達にすることが不可能ならば -1、 そうでないならば、達成するのに必要な最小コストの値として定義する。 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 の 2 名です。このとき、

  • 人 1 と異なる国に属する人気者は人 3 のみです。人 1 と 人 3 を間接的に友達にするには、それぞれコスト 15,30 を払って人 1 と人 2, 人 2 と人 3 を友達にした時がかかるコストが最小で、このとき 15+30=45 となります。
  • 人 2 と異なる国に属する人気者は人 3 のみです。コスト 30 を払って人 2 と人 3 を友達にした時が最小となります。
  • 人 3 と異なる国に属する人気者は人 2 のみです。コスト 30 を払って人 2 と人 3 を友達にした時が最小となります。
  • 人 4 と異なる国に属する人気者は人 2 のみです。人 4 と 人 2 を間接的に友達にするには、それぞれコスト 15,10 を払って人 1 と人 2, 人 1 と人 4 を友達にした時がかかるコストが最小で、このとき 15+10=25 となります。

入力例 2

3 1 3 1
1 2 3
1
1 2 1000000000

出力例 2

-1 1000000000 -1

人 1 にとって自身は間接的な友達といえますが、異なる国に属していないため、 「異なる国に属する人気者」の条件をみたす相手はいないことに注意してください。

Score : 600 points

Problem Statement

There are N people and K nations, labeled as Person 1, Person 2, \ldots, Person N and Nation 1, Nation 2, \ldots, Nation K, respectively.
Each person belongs to exactly one nation: Person i belongs to Nation A_i. Additionally, there are L popular people among them: Person B_1, Person B_2, \ldots, Person B_L are popular. Initially, no two of the N people are friends.

For M pairs of people, Takahashi, a God, can make them friends by paying a certain cost: for each 1\leq i\leq M, he can pay the cost of C_i to make Person U_i and Person V_i friends.

Now, for each 1\leq i\leq N, solve the following problem.

Can Takahashi make Person i an indirect friend of a popular person belonging to a nation different from that of Person i? If he can do so, find the minimum total cost needed. Here, Person s is said to be an indirect friend of Person t when there exists a non-negative integer n and a sequence of people (u_0, u_1, \ldots, u_n) such that u_0=s, u_n=t, and Person u_i and Person u_{i+1} are friends for each 0\leq i < n.

Constraints

  • 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.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Let X_i defined as follows: X_i is -1 if it is impossible to make Person i an indirect friend of a popular person belonging to a nation different from that of Person i; otherwise, X_i is the minimum total cost needed to do so. Print X_1, X_2, \ldots, X_N in one line, with spaces in between.

Sample Input 1

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

Sample Output 1

45 30 30 25

Person 1, 2, 3, 4 belong to Nation 1, 1, 2, 2, respectively, and there are two popular people: Person 2 and 3. Here,

  • For Person 1, the only popular person belonging to a different nation is Person 3. To make them indirect friends with the minimum cost, we should pay the cost of 15 to make Person 1 and 2 friends and pay 30 to make Person 2 and 3 friends, for a total of 15+30=45.
  • For Person 2, the only popular person belonging to a different nation is Person 3. The minimum cost is achieved by making Person 2 and 3 friends by paying 30.
  • For Person 3, the only popular person belonging to a different nation is Person 2. The minimum cost is achieved by making Person 2 and 3 friends by paying 30.
  • For Person 4, the only popular person belonging to a different nation is Person 2. To make them indirect friends with the minimum cost, we should pay the cost of 15 to make Person 1 and 2 friends and pay 10 to make Person 1 and 4 friends, for a total of 15+10=25.

Sample Input 2

3 1 3 1
1 2 3
1
1 2 1000000000

Sample Output 2

-1 1000000000 -1

Note that, for Person 1, Person 1 itself is indeed an indirect friend, but it does not belong to a different nation, so there is no popular person belonging to a different nation.