← 返回题目列表

AtCoder · abc307_f

I. 病毒2

中文机器翻译题面 查看原题

分数: 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

请注意,仅使用走廊在任意两个房间之间移动并不总是可行。