Speed Limits

Time limit1sMemory limit128 MB

Summary
Find the fastest path in a directed road network where roads without a posted speed limit inherit the previously used speed limit, requiring state-dependent shortest path search.
Level

Medium6 of 10

Topics
Shortest path, Graph, Dynamic programming
Solved
No attempts yet

Problem

When you drive, you usually care less about the shortest route than about the route that takes the least time, so the speed limit on each road matters. Some speed-limit signs, however, are missing. A driver cannot know a limit that is not posted, so the only sensible rule is that after entering a road with no sign, the driver keeps obeying the same speed limit as before.

You are given a road network of crossings and one-way roads. Each road connects exactly two crossings and carries at most one speed-limit sign, placed at the road's start. For any two crossings A and B there is at most one road from A to B. Assume acceleration is instantaneous, that no other traffic affects you, and that you never exceed the current speed limit. Compute the fastest route from the start crossing to the destination crossing.

Input

The first line contains three integers N, M and D, where N (2 ≤ N ≤ 150) is the number of crossings numbered 0 to N-1, M is the number of roads, and D is the destination crossing. Each of the next M lines contains four integers A (0 ≤ A < N), B (0 ≤ B < N), V (0 ≤ V ≤ 500) and L (1 ≤ L ≤ 500): a road from crossing A to crossing B with speed limit V and length L. If V is 0, the sign is missing. The time for a road is T = L / V when V ≠ 0, and T = L / V_prev otherwise, where V_prev is the speed limit you were obeying when you entered the road (use floating-point division). You start at crossing 0, and your initial speed limit is 70.

Output

Print one line with the crossings visited on the fastest route from 0 to D, in the exact order they are passed, starting with 0 and ending with D, separated by single spaces. The fastest route is always unique (no two routes achieve the same minimum time).

Notes

The total travel time of a route is the sum of L / V over its roads, where a road with a missing sign reuses the most recently obeyed speed limit.

Examples6

  1. Example 1

    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
    Expected output
    0 5 2 3 1

  2. Example 2

    Input
    2 1 1
0 1 10 100
    Expected output
    0 1

  3. Example 3

    Input
    2 1 1
0 1 0 140
    Expected output
    0 1

  4. Example 4

    Input
    3 2 0
0 1 10 5
1 2 10 5
    Expected output
    0

  5. Example 5

    Input
    3 3 2
0 1 10 100
1 2 10 100
0 2 10 150
    Expected output
    0 2

  6. Example 6

    Input
    4 3 3
0 1 100 10
1 3 0 100
0 3 0 100
    Expected output
    0 1 3