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

Memory Limit:32 MB Time Limit:0.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

一张 nnn 个点 mmm 条有向边的图上,有 qqq 个配送需求,需求的描述形式为 (si,ti,li,ri)( s_i , t_i , l_i , r_i )(si,ti,li,ri),即需要从点 sis_isi 送到 tit_iti, 在时刻 lil_ili 之后(包括 lil_ili )可以在 sis_isi 领取货物,需要在时刻 rir_iri 之前(包括 rir_iri)送达 tit_iti ,每个任务只需完成一次。

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

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

输入格式

第一行,三个正整数 n,m,q(2≤n≤20,1≤m≤400,1≤q≤10)n , m , q (2\leq n\leq 20, 1\leq m\leq 400, 1\leq q\leq 10)n,m,q(2n20,1m400,1q10)
接下来 mmm 行,每行三个正整数 ui,vi,ci(1≤ui,vi≤n,1≤ci≤20000)u_i , v_i , c_i (1\leq u_i,v_i\leq n, 1\leq c_i\leq 20000)ui,vi,ci(1ui,vin,1ci20000),表示有一条从 uiu_iuiviv_ivi 耗时为 cic_ici 的有向边。
接下来 qqq 行,每行四个正整数 si,ti,li,ri(1≤si,ti≤n,1≤li≤ri≤106)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)si,ti,li,ri(1si,tin,1liri106),描述一个配送任务。

输出格式

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

样例

样例输入

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 并交货。