题目描述

Your plane to the ICPC Finals departs in a short time, and the only way to get to the airport is by bus. Unfortunately, some of the bus drivers are considering going on strike, so you do not know whether you can get to the airport on time. Your goal is to plan your journey in such a way as to maximize the probability of catching your plane.

You have a detailed map of the city, which includes all the bus stations. You are at station $0$ and the airport is at station $1$ . You also have a complete schedule of when each bus leaves its start station and arrives at its destination station. Additionally, for each bus you know the probability that it is actually going to run as scheduled, as opposed to its driver going on strike and taking the bus out of service. Assume all these events are independent. That is, the probability of a given bus running as planned does not change if you know whether any of the other buses run as planned.

If you arrive before the departure time of a bus, you can transfer to that bus. But if you arrive exactly at the departure time, you will not have enough time to get on the bus. You cannot verify ahead of time whether a given bus will run as planned $-$ you will find out only when you try to get on the bus. So if two or more buses leave a station at the same time, you can try to get on only one of them.

Figure A.1 : Bus schedule corresponding to Sample Input $1$ .

Consider the bus schedule shown in Figure A.1 . It lists the start and destination stations of several bus routes along with the departure and arrival times. You have written next to some of these the probability that that route will run. Bus routes with no probability written next to them have a $100\%$ chance of running. You can try catching the first listed bus. If it runs, it will take you straight to the airport, and you can stop worrying. If it does not, things get more tricky. You could get on the second listed bus to station $2$ . It is certain to leave, but you would be too late to catch the third listed bus which otherwise would have delivered you to the airport on time. The fourth listed bus $-$ which you can catch $-$ has only a $0$ . $1$ probability of actually running. That is a bad bet, so it is better to stay at station $0$ and wait for the fifth listed bus. If you catch it, you can try to get onto the sixth listed bus to the airport; if that does not run, you still have the chance of returning to station $0$ and catching the last listed bus straight to the airport.

输入格式

The first line of input contains two integers $m (1 \le m \le 10^{6})$ and $n (2 \le n \le 10^{6}),$ denoting the number of buses and the number of stations in the city. The next line contains one integer $k (1 \le k \le 10^{18}),$ denoting the time by which you must arrive at the airport.

Each of the next $m$ lines describes one bus. Each line contains integers a and $b (0 \le$ a , $b < n$ , a $≠ b)$ , denoting the start and destination stations for the bus. Next are integers $s$ and $t (0 \le s < t \le k)$ , giving the departure time from station a and the arrival time at station $b$ . The last value on the line is $p (0 \le p \le 1$ , with at most $10$ digits after the decimal point), which denotes the probability that the bus will run as planned.

输出格式

Display the probability that you will catch your plane, assuming you follow an optimal course of action. Your answer must be correct to within an absolute error of $10^{−6}.$

题目大意

给定一个图，有 $n$ 个点和 $m$ 条有向边，你现在在 $0$ 号点，你要在 $k$ 的时间前到达 $1$ 号点。

每条边从 $a$ 连向 $b$，在 $s$ 时间到达 $a$ 就可以用 $t$ 的时间到达 $b$，如果你要从 $a$ 到达 $b$，可以选择提前到达然后在 $a$ 等待，或者刚刚好用 $s$ 的时候到达 $a$，但是超过 $s$ 的时间到达就不能通过这条边到达 $b$ 了。每条边有 $p$ 的概率不能通过。

求准时到达 $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

0.3124

4 2
2
0 1 0 1 0.5
0 1 0 1 0.5
0 1 1 2 0.4
0 1 1 2 0.2

0.7

提示

Time limit: 10 s, Memory limit: 1024 MB.

spj provider: