我大概有几天在考虑this problem的算法我想出了不同的解决方案，但没有一个得到正确的结果。我在想有向无环图，但似乎乘客可以做一个往返，例如，从0站到3站，然后从3站到0站，然后从0站到1站。如果有人能描述这个问题的算法（而不是代码），我将不胜感激为了便于查找，我也把问题放在这里。
你去ICPC决赛的飞机很快就要起飞了
去机场的路是坐公共汽车。不幸的是，有些巴士
司机们正在考虑罢工，所以你不知道
你可以准时到达机场你的目标是计划你的旅程
这样可以最大限度地抓住飞机的可能性。
你有一张详细的城市地图，包括所有的公共汽车
车站。你在0号站，机场在1号站。你
也有一个完整的时间表当每辆公共汽车离开它的开始
到达目的站。另外，对于每个
公车你知道它实际运行的概率
计划好了，而不是司机罢工坐公车
停止服务。假设所有这些事件都是独立的也就是说
如果你的车按计划行驶的概率不变
知道其他公共汽车是否按计划行驶。如果你到了
在公共汽车出发前，你可以换乘那辆公共汽车。但是
如果你正好在出发时间到达，你就吃不饱了
该上车了。你不能提前确认
给定的巴士将按计划运行-只有当你试图
上车所以如果两辆或更多的公共汽车同时离开一个车站
时间，你可以试着只上其中一个。
输入
本市车站数量下一行包含一个整数k
（1≤k≤10^18），表示您必须到达
机场。接下来的m行中的每一行描述一条总线。每条线
包含整数a和b（0≤a，b以及巴士的目的站接下来是整数s和t（0≤s
B站时间，线路上最后一个值为P（0≤P≤1，at
小数点后最多10位），表示概率
公共汽车将按计划行驶。
输出
显示你赶上飞机的概率，假设你
遵循最佳的行动方案。你的回答必须正确
绝对误差在10^-6以内。
样本输入
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
样本输出
0.3124
第一行输入包含两个整数m（1≤m≤10^6）和n
（2≤n≤10^6），表示公共汽车数量和
最佳答案
考虑与每个预定行程相关的到达事件。
如果你参加了一次到达，也就是说，如果你真的成功地完成了预定的旅行，那么你在到达时间到达车站，然后你决定从那里做什么。
如果你已经知道到达下一个目的地的最佳概率，那么你可以很容易地计算出到达目的地的最佳概率。
由于您可能到达下一个目的地的航班都是晚些到达的，如果您按时间倒序处理所有可能到达的航班，那么您可以在每次到达后计算航班到达的最佳概率，只使用您已经计算过的概率。
该过程以您首次到达0号站的最佳概率结束。
如果你在实现上很聪明，整个过程需要O（N logn）时间。
关于algorithm - 在ACM ICPC 2018世界总决赛中捕捉飞机问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53837160/