P1266 Speed Limit

In this busy society, we often do not choose the shortest road but the fastest route. While driving, the speed limit of each road becomes the key factor. Unfortunately, some speed-limit signs are missing, so you cannot know how fast you should drive. A defensible approach is to keep driving at your previous speed. Your task is to compute the fastest route between two places. You are given road traffic information for a modern city. To simplify the problem, the map includes only intersections and roads. Each road is directed, connects exactly two intersections, and has at most one speed-limit sign located at the start of the road. For any two intersections $A$ and $B$, there is at most one road from $A$ to $B$. You may assume instantaneous acceleration and no congestion or similar factors. Of course, your speed cannot exceed the current speed limit.

The first line contains 3 integers $N$, $M$, and $D$ ($2\leq N\leq 150$, $1\leq M\leq 22500$). $N$ is the number of intersections, labeled from 0 to $N-1$. $M$ is the total number of roads, and $D$ is your destination. The next $M$ lines each describe one road, with 4 integers $A$ ($0\leq A

Output a single line of integers: the sequence of intersections you pass from 0 to $D$, in order, starting with 0 and ending with $D$, separated by spaces. There is only one fastest route.

Translated by ChatGPT 5