末班车
类型:程序题

题目描述

城市里有 $n$ 个地铁站以及 $m$ 条地铁线路,地铁站依次以 $1,2,\dots,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 \le 100$。

对于所有测试点,保证:

  • $1 \le n \le 500$
  • $1 \le m \le 1000$
  • $1 \le q \le 5 \times 10^5$
  • $1 \le u_i, v_i, x_i, y_i \le n$
  • $0 \le l_i, s_i \le 10^5$
  • $1 \le t_i \le 10^4$
代码编辑器 加载中...
测试用例输入
{{resultStatus.text}}
乐编题库AI助手
人工客服
微信扫码联系客服
历史对话
{{ s.title || '未命名对话' }}
{{ s.created_at }}
暂无历史对话
我能帮助你什么?