#2014. [QkOI#R1] Quark and Flying Pigs

[QkOI#R1] Quark and Flying Pigs

题目描述

给定一个 nn 个点 mm 条边的边带权简单连通无向图,在 00 时刻你在点 11 上。

假设当前是 tt 时刻,你在点 vv 上,你可以选择两种操作:

  • 仍停留在点 vv 上,操作后到 t+1t+1 时刻。
  • 选择一条边 (a,b,w)(a,b,w) 满足 a=va=v 或 b=vb=v,则你到这条边连接的另一个点上,操作后到 t+wt+w 时刻。

有 kk 条信息,每一条信息形如 (ti,vi)(t_i,v_i) 表示在 tit_i 时刻,点 viv_i 上会出现一只飞猪,其编号为 ii,若该时刻你在 viv_i 上,则你捕获到了 ii 号飞猪。

现在你需要求出你能捕获到的飞猪数量的最大值。

输入格式

第一行为三个正整数 n,m,kn,m,k。

接下来 mm 行每行三个正整数 ai,bi,wia_i,b_i,w_i。

接下来 kk 行每行两个正整数 ti,vit_i,v_i。

输出格式

一行一个整数,为你能捕获到的飞猪数量的最大值。

样例

2 1 5
1 2 2
1 2
2 2
3 2
5 1
7 2
4

题目来源:洛谷 P6512