Lawful Limits

시간 제한2초메모리 제한1024 MB

요약

모든 도로의 제한 속도가 정해진 시각 t에 두 배로 오를 때, 1번에서 n번까지 가장 빨리 도착하는 시간을 구한다.

난이도: 보통10점 중 7점
유형: 최단 경로, 그래프, 동적 계획법
정답자: 아직 제출이 없습니다

문제

One late afternoon you are driving to get home in your Big And Pricey Car. You have had a long day and are eager to get home as soon as possible. Your country's road network has many roads with varying speed limits, and has one strange quirk: at some time $t$, the maximum speed on each road is raised. Because you want to get home as soon as possible, you instantly increase your speed to the new maximum speed of the road you are on at time $t$.

You start driving at time $0$ at junction $1$ and are going to $n$. What is the earliest time you can reach your destination? As an example, consider the first sample case, visualized in Figure L.1.

Figure L.1: Visualization of the first sample input. The edges are marked with their lengths. On all roads, the maximum speed is $1$ before time $t$ and $2$ from time $t$ onwards.

입력

The input consists of:

One line with three integers $n$, $m$, and $t$ ($2\leq n\leq10^5$, $1\leq m\leq10^5$, $0\leq t\leq10^9$), the number of junctions, the number of roads, and the time the speed limit increases.
$m$ lines, each with five integers $x$, $y$, $\ell$, $v$, and $w$ ($1\leq x,y\leq n$, $1\leq\ell\leq10^9$, $1\leq v<w\leq10^9$), the start and end junction of a road, length of this road, and the speed limits on this road before time $t$ and from time $t$ onwards.

There is at most one road between any two junctions, and one can travel in both directions on any road. No road leads from one junction to that same junction. It is guaranteed that there is always a path between any two junctions.

출력

Output the minimum amount of time it takes to get from the start to your destination.

Your answer should have an absolute or relative error of at most $10^{-6}$ .

예제3

예제 1

입력

예상 출력

1.5

예제 2
입력
```
2 1 1
1 2 3 1 2
```
예상 출력
```
2.0
```

예제 3

입력

4 4 6
1 2 30 4 6
1 3 12 6 8
2 4 16 4 8
3 4 30 5 10

예상 출력

7.0