6335 - 末班车
题目描述
城市里有 n 个地铁站以及 m 条地铁线路，地铁站依次以 1,2,\ldots,n 编号。
第 i 条地铁线路（1\le i\le m）的列车从地铁站 u_i 单向驶向地铁站 v_i，最晚发车时间为第 l_i 分钟，途中行驶需要 t_i 分钟。从第 0 分钟到第 l_i 分钟，每分钟都会有一班列车从地铁站 u_i 发出。第 x 分钟（0\le x\le l_i）发出的列车会在第 x+t_i 分钟到达地铁站 v_i，乘坐这班列车的乘客可以换乘第 x+t_i 分钟以及之后的所有从地铁站 v_i 发出的任意线路的列车。
现在有 q 组询问。第 i 组询问（1\le i\le q）给出起点地铁站编号 x_i，终点地铁站编号 y_i 以及出发时间 s_i，你需要判断第 s_i 分钟从地铁站 x_i 出发是否能到达地铁站 y_i。第 s_i 分钟从地铁站 x_i 出发意味着你可以乘坐第 s_i 分钟以及之后的所有从地铁站 x_i 发出的任意线路的列车。
输入
第一行，三个正整数 n,m,q，分别表示地铁站数量，地铁线路数量，询问数量。
接下来 m 行，每行四个整数 u_i,v_i,l_i,t_i，分别表示地铁线路的起点、终点、最晚发车时间、行驶所需时间。
接下来 q 行，每行三个整数 x_i,y_i,s_i，分别表示行程起点、行程终点、出发时间。
输出
输出共 q 行。对于每组询问，如果第 s_i 分钟从地铁站 x_i 出发能到达地铁站 y_i 则输出一行 Yes，否则输出一行 No。请注意输出区分大小写。
样例
输入
3 4 5 1 2 3 3 2 3 5 2 3 1 4 1 1 3 0 6 1 3 2 2 1 2 2 1 3 3 2 2 3 2 3
输出
Yes Yes No Yes No
说明
数据范围
对于 40\% 的测试点，保证 q\le100。
对于所有测试点，保证：
- 1\le n\le500
- 1\le m\le1000
- 1\le q\le5\times10^5
- 1\le u_i,v_i,x_i,y_i\le n
- 0\le l_i,s_i\le10^5
- 1\le t_i\le10^4
标签
