April 4th, 2010, 02:08 AM
Gassing the van problem(algorithm)
Hello CodeGuru forums,
I have come across a problem,which states as follows :
I have tried a lot to get the right answer, but i am not able to
Intro: We will be renting a van and driving somewhere in the southeast.We have very little money to work with and want to make the trip as inexpensive as possible.Figuring out the best route is easy - but what about the price of gas? There may be many gas stations along the way, with different prices. How can we minimize the cost?
Problem: Given a description of the van and the route, compute the smallest amount of money possible to spend on gas. Whenever we stop for gas we always fill the tank entirely. It might be cheaper to put in gas only to get to the next cheapest gas station, but we wont do that - thats WAY too COMPLEX.
Remember, we have got to go to the destination and come back! The amount has to be for the round trip.Assume that we do not do any driving at the destination point.Assume that we take the same route back, just in the other direction. There will always be a station at mile 0. This is the rental agency and they insist that we fill our tank when we return the van. Assume that the tank starts out at full.
The input :
There will be one or more input sets. Each set will begin with a line describing the van. it will have 2 positive integers :
tank mpg (1<=tank<=100 and 1<=mpg<=100)
which denotes the size of the van's tank in gallons, and the van's fuel efficiency in miles-per-gallon respectively.
The next line describes the route. It has two integers :
n miles (1<=n<=10000 and 1<=miles<=5000)
which denote the number of gas stations along the way, and the length of the trip, one way, in miles.
The next line n describes the gas stations, one per line. They each contain an integer and a real number.
distance cost (0<=distance<=miles , 0.000 <=cost<=100.00)
which represent the distance in miles from the beginning of the trip to this gas station, the cost in dollars of a gallon of gas here. There will always be a station at distance 0(the rental agency). When the van is returned, the tank must be filled at this station. The stations are guaranteed to be listed in nondecreasing order of distance. There is guaranteed to be a solution.
The input will end with an empty input set, with tank=mpg=0. Don't process this set.
The Output: For each input set, print the number starting with 1 and produce a single real number on its own line, with exactly two decimal places, representing the least amount in dollars and cents that gas my cost on this trip. Do not print any blank lines, Round to the nearest penny.
Sample input :
Sample output(corresponding to sample input):
Trip 1: 90.21
Trip 2: 50.00
NOW, HERE IS THE APPROACH I TOOK :
I want to apply Dijkstra's shortest path algorithm to solve this.
My biggest problem has been - how to create the graph and how to assign weights of the edges.
I created a graph with the starting point, all the gas stations along the way and the destination as nodes.
The weights were assigned by : (distance between this node and previous node) * (cost of gas at previous station)/mileage;
After applying Dijkstra algorithm from source to destination, I got a cost of 43.57, i thought since the return route is the same, just multiply by 2.
But i am not getting the answer of 90.21
Can someone please give me the shortest path and help me find out how do we reach the 90.21 figure? I dont quite understand what i am mising here.
Is my approach to the solution wrong (something wrong in creating the graph)?
It would be really great if someone could help me on this!
Tags for this Thread
Click Here to Expand Forum to Full Width