AT_abc307_f [ABC307F] Virus 2

题目描述

有 $N$ 个房间，编号为 $1, 2, \ldots, N$，每个房间里住着一人。此外，有 $M$ 条通道连接着一些不同的两个房间。第 $i$ 条通道连接房间 $U_i$ 和房间 $V_i$，长度为 $W_i$。

某一天（记为第 $0$ 天夜晚），住在房间 $A_1, A_2, \ldots, A_K$ 的 $K$ 个人被新感染了病毒。接下来的 $D$ 天里，第 $i$ 天（$1 \leq i \leq D$）病毒的传播方式如下：

在第 $(i-1)$ 天夜晚已经感染的人，在第 $i$ 天夜晚依然保持感染状态。
对于其他人，如果他们住的房间与第 $(i-1)$ 天夜晚已感染者所住的任意一个房间之间的距离不超过 $X_i$，则在第 $i$ 天夜晚新感染。这里，房间 $P$ 和房间 $Q$ 之间的距离定义为仅通过通道从 $P$ 到 $Q$ 时所经过通道长度的最小总和。如果无法仅通过通道从 $P$ 到 $Q$ 移动，则距离视为 $10^{100}$。

请对于每个 $i$（$1 \leq i \leq N$），输出住在房间 $i$ 的人是在第几天夜晚新感染的。如果到第 $D$ 天夜晚仍未感染，则输出 $-1$。

输入格式

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

$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

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

输入输出样例 #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

输入 #3

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

输出 #3

0
2
0
-1
-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$
• 所有输入均为整数

样例解释 1

病毒的传播过程如下：

• 第 $0$ 天夜晚，住在房间 $1$ 的人感染。
• 房间 $1$ 到房间 $2,3,4$ 的距离分别为 $2,3,5$。由于 $X_1=3$，所以第 $1$ 天夜晚，住在房间 $2,3$ 的人新感染。
• 房间 $3$ 到房间 $4$ 的距离为 $2$。由于 $X_2=3$，所以第 $2$ 天夜晚，住在房间 $4$ 的人也感染。
  因此，住在房间 $1,2,3,4$ 的人分别在第 $0,1,1,2$ 天新感染，按顺序输出 $0,1,1,2$。

样例解释 3

请注意，并非所有两个房间之间都一定可以仅通过通道互相到达。

由 ChatGPT 4.1 翻译