#6403. 「ICPC World Finals 2018」赶飞机

内存限制:1024 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

前往 ICPC Finals 的飞机即将起飞,并且唯一的前往机场的方式是公交车。不幸运的是,一部分公交车司机正在罢工,所以你无法确定是否能及时赶往机场。你的目标是规划你的行程来最大化赶上飞机的概率。

你有一张非常详细的地图,地图上列有所有的公交车站。你在编号为 0 的车站,而机场在编号为 1 的车站,并且你知道每辆公交车的出发时间和到达时间,以及公交车按计划运行的概率(因为公交车司机可能会罢工)。假设各个公交车的罢工事件之间条件无关,也就是说,对于任何一辆公交车,即使你知道其它的公交车是否按计划运行,该公交车按计划运行的概率也不会改变。

如果你在出发时间前到达了起点站,你便可以坐上那辆车。但如果你在出发时间时恰好到达了起点站,你就没有足够的时间上车。你无法提前预知公交车是否会按计划运行——在上车后才能判断。也就是说,如果有多辆车在同一时间出发,你只能尝试上其中的一辆车。

输入格式

第一行有两个整数 m (1 \le m \le 10^6) n (2 \le n \le 10^6) ,分别表示公交车的数量和车站的数量。

接下来一行有一个整数 k (1 \le k \le 10^{18}) ,表示你必须到达机场的时间。

接下来 m 行每行描述一个公交车。每行有两个整数 a,b (0 \le a,b \lt n,a \neq b) ,分别表示公交车的起点站和目的地。接下来两个整数 s,t (0 \le s \lt t \le k) ,表示从车站 a 的出发时间和到达车站 b 的时间。最后为一个实数 p (0 \le p \le 1) ,小数点后不超过 10 位,表示公交车按计划运行的概率。

输出格式

输出最优策略下赶上飞机的概率。你的答案的绝对误差不能超过 10^{-6} .

样例

样例输入 1

8 4
1000
0 1 0 900 0.2
0 2 100 500 1.0
2 1 500 700 1.0
2 1 501 701 0.1
0 3 200 400 0.5
3 1 500 800 0.1
3 0 550 650 0.9
0 1 700 900 0.1

样例输出 1

0.3124

样例解释 1

schedule.png

考虑上图所示的公交计划表。上面列出了几条公交路线的出发地、目的地以及出发时间和到达时间。你在部分公交车计划后面写上了该公交按计划运行的概率。没有写概率的公交车会以 100\% 的概率按计划运行。你可以先尝试第一辆列出的公交车。如果该公交车按计划运行,你便可以直接到达机场,无需担忧。但如果没有,则事情变得复杂起来。假如你上了第二辆公交车,则这辆车一定会出发,但等这辆车到站时你无法赶上第三辆公交车前往机场。你可以上第 4 辆车,但这辆车只有 0.1 的概率启动。所以更好的方案是待在 0 站并乘坐第 5 辆车。如果该车没有出发,你还有机会回到第 0 站并乘坐最后一个公交车直接前往机场。

数据范围与提示

1 \le m \le 10^6

2 \le n \le 10^6

1 \le k \le 10^{18}

在不侵犯原题版权的情况下,本题面中文翻译基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布,注明出处时需指向本题链接。