← 返回题目列表

AtCoder · past202104_g

G. 一次一步

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

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

可能有些城市无法通过公路到达。