10472 - Fastest Vs Cheapest

[ditrix]

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 auto-rickshaw price = 20 time = 7.00
2.2 taxi-cab 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?

[Alexander Grushetsky]

When you go from 0 to 2 on rickshaw, you don't let him go at 1. So you go all 12km with him, wait him and pay only once.

[kmhasan]

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.

[ditrix]

Merci for explication. I have ajusted my program and it was accepted.
And about the problem statement, it's nice

[przygoda]

okey , I found the solution , but i think i have a small mistake in my code , it is possible for anybody to give me some interestin input-s with output-s .
Tnaks very much Martin

[Endrju]

Can you give me a hint how to solve this problem? Is it Dijkstra alg. modification, or sth like that?

[kmhasan]

The judge solution generates two separate graph: one for motorized vehicles, the other one for non-motorized 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 problem-setter 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.

[makbet]

Are fractional fares possible in this problem? The table contains integer fares per 1 km, so does the point about fractional fares and paying extra have any meaning for the problem?

[ditrix]

All costs are itegers in this problem. It means, that, for ex., if you get a bus for 1km you must pay a minimum fare of 2Tk.
On the contrary the travel time can be fractional.

[makbet]

I keep getting WA. Maybe you guys have got any tricky input that might help me in finding a bug?
thanks

[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.

[makbet]

I made that mistake, but it seems that it's not the only one, because I still have WA

[Endrju]

Big thx Tomal for your hint. My solution uses 2 Dijkstras after Floyd (one for fastest routes and one for cheapest). It's not as fast as yours but IT WORKS !!

[Maxim]

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

[kmhasan]

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.