Editorialist: Kartik Kapoor http://www.codechef.com/users/kartik07
Dijkstra’s algorithm http://en.wikipedia.org/wiki/Dijkstra’s_algorithm
You are required to find the minimum amount that a person will have to pay if he is to travel
between 2 given places. The amount is calculated from the ‘points’ the person posseses at the end
of the trip, which are in-turn calculated from the distance the person travels.
This is a classic problem of finding the minimum distance between 2 places with a twist!!
QUICK EXPLANATIONThe problem can be solved by applying Dijkstra's algorithm with a slight variation as to how the
distance between 2 adjacent nodes is calculated. The distance travelled is taken as the actual
distance between the nodes minus a given value. This is value is different for different nodes. The
value is subtracted only if the distance between a pair of nodes is more than the value to be
The problem requires you to find the minimum distance between 2 nodes in a directed graph. This
can be done by applying Dijkstra’s algorithm
.Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph. Here is
another helpful link : [Dijkstra’s algorithm](http://www.geeksforgeeks.org/greedy-algorithms-set-6-
Below are the detailed steps used in Dijkstra’s algorithm to find the shortest path from a single
source vertex to all other vertices in the given graph:
1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path
tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE.
Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices
….a) Pick a vertex u which is not there in sptSetand has minimum distance value.
….b) Include u to sptSet.
….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate
through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source)
and weight of edge u-v, is less than the distance value of v, then update the distance value of v.
Finally you will need to modify the Dijkstra’s algorithm as follows:
The distance between 2 adjacent nodes is taken as the actual distance between the nodes minus a
given value. This is value is different for different nodes. The value is subtracted only if the distance
between a pair of nodes is more than the value to be subtracted.