个人中心
gpt4 book ai didi

algorithm - Catch the Plane 问题来自 ACM ICPC 2018 世界总决赛

转载 作者：塔克拉玛干 更新时间：2023-11-03 05:50:28 27 4
gpt4 key购买 nike

<分区>

这几天在思考this problem的算法.我想出了不同的解决方案，但没有一个得到正确的输出。我在考虑有向无环图，但似乎乘客可以进行往返，例如，从车站 0 到 3，然后从 3 到 0，然后从 0 到 1。如果有人能描述一下，我将不胜感激这个问题的算法(不是代码)。为了方便查找，我把问题也放在这里。

Your plane to the ICPC Finals departs in a short time, and the onlyway to get to the airport is by bus. Unfortunately, some of the busdrivers are considering going on strike, so you do not know whetheryou can get to the airport on time. Your goal is to plan your journeyin such a way as to maximize the probability of catching your plane.You have a detailed map of the city, which includes all the busstations. You are at station 0 and the airport is at station 1. Youalso have a complete schedule of when each bus leaves its startstation and arrives at its destination station. Additionally, for eachbus you know the probability that it is actually going to run asscheduled, as opposed to its driver going on strike and taking the busout of service. Assume all these events are independent. That is, theprobability of a given bus running as planned does not change if youknow whether any of the other buses run as planned. If you arrivebefore the departure time of a bus, you can transfer to that bus. Butif you arrive exactly at the departure time, you will not have enoughtime to get on the bus. You cannot verify ahead of time whether agiven bus will run as planned – you will find out only when you try toget on the bus. So if two or more buses leave a station at the sametime, you can try to get on only one of them.

Input

The first line of input contains two integers m (1 ≤ m ≤ 10^6 ) and n (2 > ≤ n ≤ 10^6 ), denoting the number of buses and the number of stations in > the city. The next line contains one integerk (1 ≤ k ≤ 10^18 ), denoting the time by which you must arrive at theairport. Each of the next m lines describes one bus. Each linecontains integers a and b (0 ≤ a, b < n, a != b), denoting the startand destination stations for the bus. Next are integers s and t (0 ≤ s< t ≤ k), giving the departure time from station a and the arrivaltime at station b. The last value on the line is p (0 ≤ p ≤ 1, with atmost 10 digits after the decimal point), which denotes the probabilitythat the bus will run as planned.

Output

Display the probability that you will catch your plane, assuming youfollow an optimal course of action. Your answer must be correct towithin an absolute error of 10^−6 .

Sample Input

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

Sample Output

0.3124

27 4 0
文章推荐： algorithm - 对于 "small"数据集，插入排序是一个不错的选择。什么是 "small"？
文章推荐： php - 实时更新后获取数据
文章推荐： php - PHP 脚本中的损坏堆
文章推荐： algorithm - 以下算法的复杂性
塔克拉玛干
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com