#6177. 「美团 CodeM 初赛 Round B」送外卖2

内存限制:32 MiB 时间限制:200 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

一张 n 个点 m 条有向边的图上,有 q 个配送需求,需求的描述形式为 ( s_i , t_i , l_i , r_i ) ,即需要从点 s_i 送到 t_i , 在时刻 l_i 之后(包括 l_i )可以在 s_i 领取货物,需要在时刻 r_i 之前(包括 r_i )送达 t_i ,每个任务只需完成一次。

图上的每一条边均有边权,权值代表通过这条边消耗的时间。在时刻 0 有一个工作人员在点 1 上,求他最多能完成多少个配送任务。

在整个过程中,可以认为领货跟交货都是不消耗时间的,时间只花费在路程上。当然在一个点逗留也是允许的。

输入格式

第一行,三个正整数 n , m , q (2\leq n\leq 20, 1\leq m\leq 400, 1\leq q\leq 10)
接下来 m 行,每行三个正整数 u_i , v_i , c_i (1\leq u_i,v_i\leq n, 1\leq c_i\leq 20000) ,表示有一条从 u_i v_i 耗时为 c_i 的有向边。
接下来 q 行,每行四个正整数 s_i , t_i , l_i , r_i (1\leq s_i,t_i\leq n, 1\leq l_i\leq r_i\leq 10^6) ,描述一个配送任务。

输出格式

一个整数,表示最多能完成的任务数量。

样例

样例输入

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

样例输出

2

样例解释

工作人员可以在时刻 1 到达点 2 ,领取第二个货物后在时刻 2 到达点 3 后交货,逗留到时刻 4 ,领取第三个货物,在时刻 4 到达点 4 并交货。