P7271 [BalticOI 2002] Speed Limits (Day1)

You are now at node $0$ in an undirected graph with $N$ nodes and $M$ edges. The $N$ nodes are numbered from $0$ to $N-1$. Each edge connects $A$ and $B$, with speed limit $V$ and length $L$. The time to pass this edge is computed as follows: $$T=\begin{cases}\dfrac{L}{V}\ (V\ne 0)\\\dfrac{L}{V_\text{old}}\ (V=0)\end{cases}$$ Here, $V_\text{old}$ is the value of $V$ on the previous edge you passed. Initially, $V_\text{old}=70$. If $V=0$, then after computing $T$, the value of $V$ on this edge is updated to $V_\text{old}$, and $V_\text{old}$ is updated to $V$. You want to go from node $0$ to node $D$. Find a path from $0$ to $D$ that minimizes the total travel time.

The first line contains three integers $N,M,D$, representing the number of nodes, the number of edges, and the destination node. The next $M$ lines each contain four integers $A,B,V,L$, representing an edge.

Output one line with several integers, representing a path with the minimum total travel time.

#### Sample Explanation For sample $1$, the time spent on the output path is the smallest, which is $2628$. #### Constraints For $100\%$ of the testdata, $2 \le M \le N \le 150$, $0 \le V,L \le 500$. #### Note Translated from [BalticOI 2002 Day1 A Speed Limits](https://boi.cses.fi/files/boi2002_day1.pdf)。 Translated by ChatGPT 5