## 10472 - Fastest Vs Cheapest

Moderator: Board moderators

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

### 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.1 rickshaw price = 5, time = 8.00
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?
@+!
DitriX

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
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
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
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.

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris
Merci for explication. I have ajusted my program and it was accepted.
And about the problem statement, it's nice
@+!
DitriX

przygoda
New poster
Posts: 7
Joined: Fri Aug 09, 2002 12:26 pm
Location: Poland
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
New poster
Posts: 4
Joined: Sat Mar 15, 2003 3:23 pm
Location: Poland
Can you give me a hint how to solve this problem? Is it Dijkstra alg. modification, or sth like that?

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:
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
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
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
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris
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.
@+!
DitriX

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
I keep getting WA. Maybe you guys have got any tricky input that might help me in finding a bug?
thanks

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:
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
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
I made that mistake, but it seems that it's not the only one, because I still have WA

Endrju
New poster
Posts: 4
Joined: Sat Mar 15, 2003 3:23 pm
Location: Poland
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
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

### 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

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am