33OJ
登录 注册

#P7271. [BalticOI 2002] Speed Limits (Day1)

[BalticOI 2002] Speed Limits (Day1)

Problem Description

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 AA and BB, there exists at most one road from AA to BB. 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.

Input Format

The first line of the input file speed.in consists of three integers NN, MM and DD, where NN (2≤N≤1502 \le N \le 150) is the number of crossings numbered from 00 to N−1N-1, MM is the number of roads and DD is the label of the crossing that is your destination.

Each of the following MM lines of the input file describes one road. Every line consists of four integers AA (0≤A<N0 \le A < N), BB (0≤B<N0 \le B < N), VV (0≤V≤5000 \le V \le 500) and LL (1≤L≤5001 \le L \le 500), signifying that the road goes from the crossing labelled by AA to crossing BB, has speed limit VV and length LL. If VV is zero, this means that the speed limit sign is missing. The time TT taken for a given road is thus T=LVT = \frac{L}{V} if V≠0V \neq 0, otherwise T=LVoldT = \frac{L}{V_{old}}, where VoldV_{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 00 and your current speed is 7070.

Output Format

The output file speed.out must consist of one single line of integers, describing the crossings you pass on the fastest possible path from 00 to DD. The crossings should be written in the exact order in which you pass them, starting with 00 and ending with DD. There will never be two fastest paths taking the same time.

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

Hint

Sample Explanation

For sample 11, the time spent on the output path is the smallest, which is 26282628.

Constraints

For 100%100\% of the testdata, 2≤M≤N≤1502 \le M \le N \le 150, 0≤V,L≤5000 \le V,L \le 500.