#P18937. [Mladen Manev 2019 A2] traffic / 交通流

[Mladen Manev 2019 A2] traffic / 交通流

交通流(Traffic)

题目描述

有 NN 个路口和 MM 条有向道路。道路 (u,v,l,s)(u,v,l,s) 表示:车辆从 uu 出发后经过 ll 分钟抵达 vv;每一个整数时刻,这条道路最多允许 ss 辆车从起点出发。

初始时刻0有 KK 辆车在路口1。车辆可以在路口等待任意整数分钟,也可以到达后立即继续前进。等待不产生额外容量限制。

给定截止时间 TT:如果全部 KK 辆车能在 TT 分钟内抵达路口 NN,输出所需的最短时间;否则输出无论如何安排都无法在截止时间前抵达的最少车辆数。

输入格式

第一行四个整数 N,M,K,TN,M,K,T。接下来 MM 行每行四个整数 u,v,l,su,v,l,s,描述一条道路。

输出格式

输出一个整数,按题目要求表示最短时间或最少未抵达车辆数。两种情况不另外输出标记。

数据范围

1≤NT≤100001\le N T\le10000,1≤M,K≤100001\le M,K\le10000,1≤u,v≤N1\le u,v\le N,u≠vu\ne v,1≤l≤2001\le l\le200,1≤s≤30001\le s\le3000。

样例

5 5 10 10
1 2 2 2
2 3 1 1
2 4 1 1
4 5 2 4
3 5 2 4
9

说明

可以将全部10辆车安排在第9分钟及之前到达,且无法更早让全部车辆到达。

来源与数据说明

2019 年 Dr. Mladen Manev,A2,原题名 traffic。赛事资料,原文题面见附件 statement.pdf。

本题使用官方原始测试数据;评测接口按本站环境适配。总分为 100 分。