103075: [Atcoder]ABC307 F - Virus 2

Problem Statement

There are $N$ rooms numbered $1$, $2$, $\ldots$, $N$, each with one person living in it, and $M$ corridors connecting two different rooms. The $i$-th corridor connects room $U_i$ and room $V_i$ with a length of $W_i$.

One day (we call this day $0$), the $K$ people living in rooms $A_1, A_2, \ldots, A_K$ got (newly) infected with a virus. Furthermore, on the $i$-th of the following $D$ days $(1\leq i\leq D)$, the infection spread as follows.

People who were infected at the end of the night of day $(i-1)$ remained infected at the end of the night of day $i$.
For those who were not infected, they were newly infected if and only if they were living in a room within a distance of $X_i$ from at least one room where an infected person was living at the end of the night of day $(i-1)$. Here, the distance between rooms $P$ and $Q$ is defined as the minimum possible sum of the lengths of the corridors when moving from room $P$ to room $Q$ using only corridors. If it is impossible to move from room $P$ to room $Q$ using only corridors, the distance is set to $10^{100}$.

For each $i$ ($1\leq i\leq N$), print the day on which the person living in room $i$ was newly infected. If they were not infected by the end of the night of day $D$, print $-1$.

Constraints

• $1 \leq N\leq 3\times 10^5$
• $0 \leq M\leq 3\times 10^5$
• $1 \leq U_i < V_i\leq N$
• All $(U_i,V_i)$ are different.
• $1\leq W_i\leq 10^9$
• $1 \leq K\leq N$
• $1\leq A_1<A_2<\cdots<A_K\leq N$
• $1 \leq D\leq 3\times 10^5$
• $1\leq X_i\leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$U_1$ $V_1$ $W_1$
$U_2$ $V_2$ $W_2$
$\vdots$
$U_M$ $V_M$ $W_M$
$K$
$A_1$ $A_2$ $\ldots$ $A_K$
$D$
$X_1$ $X_2$ $\ldots$ $X_D$

Output

Print $N$ lines.
The $i$-th line $(1\leq i\leq N)$ should contain the day on which the person living in room $i$ was newly infected.

Sample Input 1

4 4
1 2 2
2 3 1
2 4 3
3 4 2
1
1
2
3 3

Sample Output 1

0
1
1
2

The infection spreads as follows.

• On the night of day $0$, the person living in room $1$ gets infected.
• The distances between room $1$ and rooms $2,3,4$ are $2,3,5$, respectively. Thus, since $X_1=3$, the people living in rooms $2$ and $3$ are newly infected on the night of day $1$.
• The distance between rooms $3$ and $4$ is $2$. Thus, since $X_2=3$, the person living in room $4$ also gets infected on the night of day $2$.

Therefore, the people living in rooms $1,2,3,4$ were newly infected on days $0,1,1,2$, respectively, so print $0,1,1,2$ in this order on separate lines.

Sample Input 2

7 7
1 2 2
2 3 3
3 4 1
4 5 1
5 6 3
3 7 1
4 7 1
2
1 6
2
2 3

Sample Output 2

0
1
2
-1
2
0
-1

Sample Input 3

5 1
1 2 5
2
1 3
3
3 7 5

Sample Output 3

0
2
0
-1
-1

Note that it is not always possible to move between any two rooms using only corridors.

问题描述

有$N$个房间，编号为$1$，$2$，$\ldots$，$N$，每个房间都有一人居住，还有$M$条走廊连接两个不同的房间。第$i$条走廊将房间$U_i$和房间$V_i$连接起来，长度为$W_i$。

有一天（我们称之为第$0$天），住在房间$A_1, A_2, \ldots, A_K$的$K$人（新）感染了一种病毒。此外，在接下来的$D$天（$1\leq i\leq D$）中，感染以以下方式传播。

在第$(i-1)$天晚上结束时被感染的人在第$i$天晚上结束时仍然被感染。
对于那些没有被感染的人，只有当他们在第$(i-1)$天晚上结束时居住在一个距离至少一个被感染的人居住的房间距离不超过$X_i$的房间时才会被新感染。 这里，房间$P$和$Q$之间的距离定义为从房间$P$移动到房间$Q$时，仅使用走廊时可能的最小走廊长度之和。 如果无法仅使用走廊从房间$P$移动到房间$Q$，则距离设置为$10^{100}$。

对于每个$i$（$1\leq i\leq N$），打印住在房间$i$的人被新感染的那一天。如果在第$D$天晚上结束时他们还没有被感染，打印$-1$。

约束条件

• $1 \leq N\leq 3\times 10^5$
• $0 \leq M\leq 3\times 10^5$
• $1 \leq U_i < V_i\leq N$
• 所有$(U_i,V_i)$都不同。
• $1\leq W_i\leq 10^9$
• $1 \leq K\leq N$
• $1\leq A_1<A_2<\cdots<A_K\leq N$
• $1 \leq D\leq 3\times 10^5$
• $1\leq X_i\leq 10^9$
• 所有输入值都是整数。

输入

输入从标准输入按照以下格式给出：

$N$ $M$
$U_1$ $V_1$ $W_1$
$U_2$ $V_2$ $W_2$
$\vdots$
$U_M$ $V_M$ $W_M$
$K$
$A_1$ $A_2$ $\ldots$ $A_K$
$D$
$X_1$ $X_2$ $\ldots$ $X_D$

输出

打印$N$行。
第$i$行（$1\leq i\leq N$）应该包含住在房间$i$的人被新感染的那一天。

样例输入 1

4 4
1 2 2
2 3 1
2 4 3
3 4 2
1
1
2
3 3

样例输出 1

0
1
1
2

感染的传播如下：

• 在第$0$天晚上，住在房间$1$的人被感染。
• 房间$1$和房间$2,3,4$之间的距离分别是$2,3,5$。因此，由于$X_1=3$，住在房间$2$和$3$的人在第$1$天晚上被新感染。
• 房间$3$和$4$之间的距离是$2$。因此，由于$X_2=3$，住在房间$4$的人也在第$2$天晚上被感染。

因此，住在房间$1,2,3,4$的人分别在第$0,1,1,2$天被新感染，因此按照顺序在不同的行上打印$0,1,1,2$。

样例输入 2

7 7
1 2 2
2 3 3
3 4 1
4 5 1
5 6 3
3 7 1
4 7 1
2
1 6
2
2 3

样例输出 2

0
1
2
-1
2
0
-1

样例输入 3

5 1
1 2 5
2
1 3
3
3 7 5

样例输出 3

0
2
0
-1
-1

请注意，不一定总是可以通过仅使用走廊在任何两个房间之间移动。