← 返回题目列表

AtCoder · codequeen2024_final_d

G. 参加许多活动

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

配点 : 450 点

問題文

在 AtCoder Land 有 N 一个地点和 M 条道路。i 第 个道路连接地点 a_i 和 b_i 双向,通行需要 d_i 分钟。

接下来,在 AtCoder Land 将 K 举办 个活动。i 参加第 个活动,需要在时刻 t_i 分钟到达地点 c_i 。活动持续时间为 0 分钟。

你在时刻 0 分钟到达地点 1 在。请在适当行动时,求出最多可以参加多少个活动。

制約

  • 1 \leq N \leq 1000
  • 0 \leq M \leq 1000
  • 1 \leq K \leq 1000
  • 1 \leq a_i < b_i \leq N
  • i \neq j 的话 (a_i, b_i) \neq (a_j, b_j)
  • 1 \leq d_i \leq 10^9
  • 1 \leq c_i \leq N
  • 1 \leq t_i \leq 10^9
  • i \neq j 的话 (c_i,t_i) \neq (c_j,t_j)
  • 输入全部为整数

入力

输入将以以下形式从标准输入给出。

N M K
a_1 b_1 d_1
a_2 b_2 d_2
\vdots
a_M b_M d_M
c_1 t_1
c_2 t_2
\vdots
c_K t_K

出力

输出答案。


入力例 1

3 3 3
1 2 1
1 3 3
2 3 7
1 8
2 2
3 7

出力例 1

2

例如,通过如下行动,2 可以参加某个活动。

  • 开始时,时间 0 分钟到达地点 1 在
  • 道 1 经过时间 1 分钟到达地点 2 在
  • 時刻 2 分钟到达地点 2 参加活动 参加 2 因为不能参加超过
  • 道 1 经过时间 3 分钟到达地点 1 在
  • 道 2 经过时间 6 分钟到达地点 3 在
  • 時刻 7 分钟到达地点 3 参加活动 参加 3 因为不能参加超过

3 个活动,所以答案是 2 。


入力例 2

1 0 2
1 1
1 100

出力例 2

2

由于不存在道路,从地点 1 无法移动,但在地点 1 举行了 2 可以参加某个活动。


入力例 3

5 8 10
1 2 149622151
1 4 177783960
4 5 118947237
1 3 33222944
1 5 295060863
3 5 110881471
2 3 34104208
3 4 273071547
2 650287940
4 839296263
3 462224593
1 492601449
4 384836991
1 191890310
5 576823355
3 782177068
3 404011431
1 818008580

出力例 3

6