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 :
20 30
10 1000
0 3.459
5 1.789
6 1.879
10 1.929
103 1.129
213 1.459
512 1.349
731 1.789
816 1.449
934 1.999
35 20
1 100
0 5.000
0 0

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!

Quote:

---

Originally Posted by maheshrang

I created a graph with the starting point, all the gas stations along the way and the destination as nodes.

---

Which edges are there in the graph?

Hello,
The edges are created if the distance between 2 nodes is less than 600 miles (mileage of the van * capacity of tank)
So there is a edge from starting point to gas station 1,2,3,4,5,6, but not to 7.,8,9.
Similarly for 2 there is edge to 1,3,4,5,6 but not 7,8,9
and so on and so forth.

Quote:

---

Originally Posted by maheshrang

The weights were assigned by : (distance between this node and previous node) * (cost of gas at previous station)/mileage;

---

Shouldn't you use the cost of the gas station at the head (i.e. the one you're driving to)?
Given that you start and must end with a full tank, you'll always have to fill up after you've driven a while.

Hello,
If i am using the cost of the station I am driving to, then since there is no gas station at the destination, how do I calculate the cost of gas there?
How do I calculate the return trip?

Quote:

---

Originally Posted by maheshrang

Hello,
If i am using the cost of the station I am driving to, then since there is no gas station at the destination, how do I calculate the cost of gas there?
How do I calculate the return trip?

---

Just view the whole thing as a single trip, not as two separate trips. If the destination doesn't have a gas station, then don't include it as a node. Instead include every gas station twice, once on the way to your destination and once on the way back.