10472  Fastest Vs Cheapest
Moderator: Board moderators
10472  Fastest Vs Cheapest
Case#4:

from 0 to 1 there is only one way (on rickshaw) :
price = 23, time = 62.00
from 1 to 2 there are many ways:
1. by road "N":
1.1 rickshaw price = 5, time = 8.00
2. by road "M"
2.1 autorickshaw price = 20 time = 7.00
2.2 taxicab price = 20 time = 11.40
2.3 bus price = 2 time = 33.00
So the right solution is:
Fastest: price = 43, time = 69.00
Cheapest: price = 25, time = 95.00
But the sample output for this case is:
Case#4
25 68.00
25 68.00
Is my reasonement correct?
What do you think about?

from 0 to 1 there is only one way (on rickshaw) :
price = 23, time = 62.00
from 1 to 2 there are many ways:
1. by road "N":
1.1 rickshaw price = 5, time = 8.00
2. by road "M"
2.1 autorickshaw price = 20 time = 7.00
2.2 taxicab price = 20 time = 11.40
2.3 bus price = 2 time = 33.00
So the right solution is:
Fastest: price = 43, time = 69.00
Cheapest: price = 25, time = 95.00
But the sample output for this case is:
Case#4
25 68.00
25 68.00
Is my reasonement correct?
What do you think about?
@+!
DitriX
DitriX

 New poster
 Posts: 28
 Joined: Wed Jul 31, 2002 10:33 am
 Location: Ukraine
 Contact:
Grushetsky is almost right.
When you're at 0, you wait for 2 minutes to get a rickshaw. You take it all the way (11 km) to reach 2.
Thus, the total time spent is 68 minutes (2 minutes for waiting + 66 minutes for travelling 11 km).
I took time to prepare the input/ouput/solution for this particular problem. So I'm quite sure that they are correct. However, it may be that the lengthy problem statement and the description of unfamiliar vehicles in this weird transport system is causing some confusion.
When you're at 0, you wait for 2 minutes to get a rickshaw. You take it all the way (11 km) to reach 2.
Thus, the total time spent is 68 minutes (2 minutes for waiting + 66 minutes for travelling 11 km).
I took time to prepare the input/ouput/solution for this particular problem. So I'm quite sure that they are correct. However, it may be that the lengthy problem statement and the description of unfamiliar vehicles in this weird transport system is causing some confusion.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/
The judge solution generates two separate graph: one for motorized vehicles, the other one for nonmotorized vehicles. It then uses Floyd Warshall's all pair shortest path algorithm to get all the min distances. Then its a simple breadth first search, once to find the fastest path, then the cheapest path.
The problemsetter is dying to use dijkstra (instead of the bfs) to beat the better ranked times for this problem.
Any other innovative idea could also help.
The problemsetter is dying to use dijkstra (instead of the bfs) to beat the better ranked times for this problem.
Any other innovative idea could also help.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/
Just remembered one from Adrians pm.
To find the cheapest route, you may need to take one vehicle, travel some distance, get out of it and take the same type of vehicle again.
I found this out while testing an alternate judge solution. So far the problem statement is concerned, this case is perfectly alright. Thanks to Adrian for reminding me of it.
To find the cheapest route, you may need to take one vehicle, travel some distance, get out of it and take the same type of vehicle again.
I found this out while testing an alternate judge solution. So far the problem statement is concerned, this case is perfectly alright. Thanks to Adrian for reminding me of it.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/
Travel fare in fastest route
I've managed to calculate travel time in fastest route. What is the easiest way of finding value of travel fare in that route?
Maxim
Maxim
The easiest way to deal with it is to calculate both the time and the fare at the same time. As you'd see, the fare is not a function of the time alone. It depends on the distance of the roads and the mode of transport as well.
I simply used 2 parameters (instead of the time only) for the states of BFS. One parameter stored the time taken to come to the ith intersection, the other one stored the fare. I found the optimum (fastest or cheapest) solution based on these two parameters of a state.
I simply used 2 parameters (instead of the time only) for the states of BFS. One parameter stored the time taken to come to the ith intersection, the other one stored the fare. I found the optimum (fastest or cheapest) solution based on these two parameters of a state.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/