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$ 的人在第几天被新感染。

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

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

提示

$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$ 所有输入值均为整数。感染按如下方式传播。

在第 $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$。
注意并非总能仅使用走廊在任意两间房间之间移动。

标签: AtCoder|abc307F

来源

AtCoder|abc307F