Baltic Olympiad in Informatics: 2002 Day 1, Problem 1

In our busy world, we are not usually interested in taking the shortest path, but rather the path that takes the shortest time. When driving a car, this means that the speed limits on different roads are crucial. Imagine now that some speed limit signs are missing. Since you cannot expect the driver to know speed limits by heart, the only reasonable conclusion is that whatever speed limit he/she obeyed before will still hold after passing a missing sign. You are to write a program that calculates the fastest path by taking advantage of the missing signs.

You are given a description of the road network in a highly motorized area. To make things easier the network consists of crossings and roads. Every road is one-way, connects exactly two crossings and has at most one speed limit sign, located in the beginning of the road. For any two crossings $A$ and $B$, there exists at most one road from $A$ to $B$. You may assume that acceleration is instantaneous and that no other traffic will affect you. And of course you never drive faster than the current speed limit.

Constraints

$2\le N\le 150$

$0\le D,A,B<N$

$0\le V\le 500$

$1\le L\le 500$

Input Specification

The first line of input consists of three space-separated integers $N$, $M$ and $D$, where $N$ is the number of crossings numbered from $0$ to $N-1$, $M$ is the number of roads, and $D$ is the label of the crossing that is your destination.

Each of the following $M$ lines describes one road. Every line consists of four space-separated integers $A$, $B$, $V$ and $L$, signifying that the road goes from the crossing labelled by $A$ to crossing $B$, has speed limit $V$ and length $L$. If $V$ is zero, this means that the speed limit sign is missing. The time $T$ taken for a given road is thus $T=\frac{L}{V}$ if $V\ne 0$, otherwise $T=\frac{L}{V_{\text{old}}}$, where $V_{\text{old}}$ is the speed limit you obeyed before you arrived at the crossing. Note that the division should be done with floating-point numbers to avoid unnecessary rounding. In the beginning you are at crossing $0$ and your current speed is $70$.

Output Specification

Output one single line of space-separated integers, describing the crossings you pass on the fastest possible path from $0$ to $D$. The crossings should be written in the exact order in which you pass them, starting with $0$ and ending with $D$. There will never be two fastest paths taking the same time.

Sample Input

6 15 1
0 1 25 68
0 2 30 50
0 5 0 101
1 2 70 77
1 3 35 42
2 0 0 22
2 1 40 86
2 3 0 23
2 4 45 40
3 1 64 14
3 5 0 23
4 1 95 8
5 1 0 84
5 2 90 64
5 3 36 40

Sample Output

0 5 2 3 1

Explanation for Sample

The required time is in this case $2.628$ units.