POJ 3635 - Full Tank?
Problem : Each vertice has a price per unit for fuel. Go from u to v cost some fuel. Now given the fuel capacity of car, calculate the cheapest schedule from s to t.
Solution : Do the bfs, Let S = { (s, 0) }, T=empty. Each time choose the smallest price cost of (v, fuel) from S. Start from (v, fuel) and go to all the vertice not in T it can reach without add fuel. All the issued vertices' best price is as the same with (v, fuel). Put them to T (and if in S, erase them), and add each (u, f+1) ((u, f) is one of the issued vertice) to S whose cost is counted as the cost of (v, fuel) plus the unit fuel price of u.
Proof : With the following lemma, using induction can prove the correctness of the best price for any (u, f).
=========================
Lemma : smallest cost[u][f] is always smaller than cost[u][f+1].
Proof of Lemma : 1. If cost[u][f+1] is from cost[u][f], it must be correct. 2. If cost[u][f+1] is from other vertice, do the reverse search until find the vertice where is the place to add the fuel. If add less fuel by one, it can reach (u, f) with cost' which is smaller than cost[u][f+1]. And with definition, cost[u][f]<=cost'. []