#P18937. [Mladen Manev 2019 A2] traffic / 交通流
[Mladen Manev 2019 A2] traffic / 交通流
交通流(Traffic)
题目描述
有 个路口和 条有向道路。道路 表示:车辆从 出发后经过 分钟抵达 ;每一个整数时刻,这条道路最多允许 辆车从起点出发。
初始时刻0有 辆车在路口1。车辆可以在路口等待任意整数分钟,也可以到达后立即继续前进。等待不产生额外容量限制。
给定截止时间 :如果全部 辆车能在 分钟内抵达路口 ,输出所需的最短时间;否则输出无论如何安排都无法在截止时间前抵达的最少车辆数。
输入格式
第一行四个整数 。接下来 行每行四个整数 ,描述一条道路。
输出格式
输出一个整数,按题目要求表示最短时间或最少未抵达车辆数。两种情况不另外输出标记。
数据范围
,,,,,。
样例
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 分。