分数: 6 点
警告
2021 年 4 月 24 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
在一些国家,有 N 城市称为 City 1 穿越城市 N 和 M 道路称为路 1 直通路 N.
路 i 连接城市 A_i 和城市 B_i 双向,并且需要 C_i 遍历它的时间单位。
在城市 1,您将开始 Q一日游。上 i- 第一天,您执行以下操作之一:
- 什么都不做。
- 选择一条从您所在城市出发的道路,然后穿过该道路到达另一端的城市。在这里,最多需要 X_i 穿越所选道路的时间单位。
对于每个整数 i 来自 1 通过 Q,查找您可能位于的城市数量 i第一个晚上。
假设一个时间单位短于 \frac{1}{10^{100}} 天。
约束
- 2 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- 1 \le Q \le 2 \times 10^5
- 1 \le A_i < B_i \le N
- (A_i, B_i) \neq (A_j, B_j) 为 i \neq j
- 1 \le C_i \le 10^9
- 1 \le X_i \le 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M Q
A_1 B_1 C_1
A_2 B_2 C_2
A_3 B_3 C_3
\hspace{25pt} \vdots
A_M B_M C_M
X_1 X_2 X_3 \dots X_Q
输出
打印 Q 行。 的 i第行应包含您可能位于的城市数量 i第一个晚上。
示例输入 1
3 3 4 1 2 7 1 3 3 2 3 5 2 4 6 8
示例输出 1
1 2 3 3
- 天 1:
没有从 City 出发的道路 1 最多取 2 单位的时间要遍历,所以你必须呆在那里。
晚上您可能会去的城市只有一个: 城市 1. - 天 2:
唯一的道路 2 可用,带您前往城市 3。您也可以选择入住城市 1.
您晚上可能会去两个城市: 城市 1 和 3. - 天 3:
道路 2 和 3 可用(如果您位于他们所在的城市)。如果你搬到城市 3 前一天,可以使用路 3 到达城市 2 这一天。
您晚上可能会去三个城市: 城市 1, 2,和 3. - 天 4:
所有道路均可用,但夜间仍有可能进入三个城市: 城市 1, 2,和 3.
示例输入 2
5 7 5 1 2 6 2 3 4 1 3 3 1 4 1 3 4 6 3 5 5 1 5 9 1 5 4 3 5
示例输出 2
2 3 4 4 5
请注意,您无法在一天内穿越多条道路。
示例输入 3
4 1 3 1 4 100 50 100 1000000000
示例输出 3
1 2 2
可能有些城市无法通过公路到达。