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 )(s​i​​,t​i​​,l​i​​,r​i​​)，即需要从点 sis_is​i​​ 送到 tit_it​i​​， 在时刻 lil_il​i​​ 之后（包括 lil_il​i​​ ）可以在 sis_is​i​​ 领取货物，需要在时刻 rir_ir​i​​ 之前（包括 rir_ir​i​​）送达 tit_it​i​​ ，每个任务只需完成一次。

图上的每一条边均有边权，权值代表通过这条边消耗的时间。在时刻 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(2≤n≤20,1≤m≤400,1≤q≤10)。
接下来 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)u​i​​,v​i​​,c​i​​(1≤u​i​​,v​i​​≤n,1≤c​i​​≤20000)，表示有一条从 uiu_iu​i​​ 到 viv_iv​i​​ 耗时为 cic_ic​i​​ 的有向边。
接下来 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)s​i​​,t​i​​,l​i​​,r​i​​(1≤s​i​​,t​i​​≤n,1≤l​i​​≤r​i​​≤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 并交货。

SubmitSubmit RecordStatisticsShowOff!