分数: 550 点
问题陈述
有 N 房间编号 1, 2, \ldots, N,每个里面都有一个人居住,并且 M 连接两个不同房间的走廊。的 i第走廊连接房间 U_i 和房间 V_i 长度为 W_i.
有一天(我们称这一天 0), K 住在房间里的人 A_1, A_2, \ldots, A_K (新)感染了病毒。此外,关于 i- 以下各项 D 天 (1\leq i\leq D),感染传播如下。
一天晚上结束时被感染的人 (i-1) 在一天晚上结束时仍然受到感染 i.
对于那些没有被感染的人,当且仅当他们住在距离 X_i 来自至少一个受感染者在一天晚上所居住的房间 (i-1)。 这里,房间之间的距离 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 is 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
请注意,仅使用走廊在任意两个房间之间移动并不总是可行。