当前没有测试数据。

F - 病毒 2

得分 : $550$ 分

题目描述

有 $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$ 的房间的人才会被新感染。 这里，房间 $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$ 的人被新感染的天数。

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

0
1
1
2

感染传播如下。

• 第 $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$。

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

0
1
2
-1
2
0
-1

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

0
2
0
-1
-1

注意，不能总是只使用走廊在任意两个房间之间移动。