Last Updated: 21 Feb, 2021
Saving Money
Moderate
Asked in companies
Ninja likes to travel a lot, but at the same time, he wants to save as much money as possible.
There are ‘N’ Stations connected by ‘M’ Trains. Each train that he boards starts from station ‘A’ and reaches destination station ‘B’ with a ticket price ‘P’.
Your task is to return the cheapest price from the given ‘source’ to ‘destination’ with up to ‘K’ stops. If there is no such route, return ‘-1’.
For example:
Input:
5 6
0 1 10
0 2 10
0 3 40
1 4 10
2 4 20
4 3 5
0 3 40
There are three ways to reach station ‘3’ from station ‘0’. The first path is 0->1->4->3, which will cost us 10+ 10+ 5= 25 and the second path 0->2->4->3 will cost us, 10+ 20+ 5 = 35, and the third path 0->3 will cost us 40.
We can’t take the first path since K = 1 and in this path, we are taking 2 stops, at station ‘1’ and station ‘4’.
Similarly, there are 2 stops in the second path. Hence we’ll finally choose the 3rd path i.e. 0->3, which is colored in blue.
Input Format :
The first line contains two space-separated integers, 'N' and 'M', the number of stations and the number of trains, respectively.
The next ‘M’ line has three space-separated integers, the source stations, the destination station, and the ticket price for traveling from this source to this destination.
The final line contains three space-separated integers, the source station, the destination station, and ‘K’, the maximum number of stations at which Ninja can stop.
Output Format :
The only line that contains the cheapest price from the given ‘source’ to ‘destination’ with up to ‘K’ stops or -1 if there is no such route.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Approaches
Depth-First Search is a graph traversal algorithm where we start from the root node and visits as far as possible along each branch before backtracking. We can modify our Dfs algorithm to break cycles i.e to avoid preprocessing of already preprocessed nodes.
Algorithm
- Create an adjacency list ‘adjList’ to store the stations and the distance between them.
- Make a boolean array ‘visited’ to avoid preprocessing of already preprocessed nodes, and another integer variable ‘price’ initialized it to an infinite value(INT_MAX), which will store our ticket price.
- Make another 2 Dimensional array of ‘tickets’, which will store the price of the tickets.
- Now we’ll perform a Depth-first search from our source station using a helper function savingMoneyHelper() which will have the adjacency List(adjList), the boolean array(visited), the source, the destination, the 2-dimensional array(tickets), price of the ticket, the number of stops(K), and the cost of the current path(currentPrice) as its parameters.
- If K < -1, we’ll stop. Here we’re checking if K < -1 because we decrease K value each time by 1 only after making a call to the next node.
- If source = destination, i.e we have reached our destination, update price = min(price,currentPrice).
- If none of the above two conditions is met, update visited[source] = true, i.e marking this current node as visited.
- Now run a loop(loop variable i) to traverse all the adjacent nodes. You need to traverse only when visited[adj[source][i]] = false.
- Update visited[source] = false (backtrack).
- Finally check if price = infinite value(INT_MAX), if this condition is true, return ‘1’ else return ‘price’.
We can generate the shortest path tree where the root will be our source station and the best way to do this is to use Dijkstra’s Algorithm for finding the shortest path between nodes in a graph.
Algorithm:
- Create an adjacency list to store the stations and the distance between them. We can use a vector ‘adjList’ to achieve this.
- Make a priority queue(Minheap) pq, which will be based on the price of the ticket from source to destination, and push {0, source, K+1} into this minheap.
- Run a loop while heap is not empty
- Make a variable ‘node’ = pq.top() and perform the pq.pop() operation.
- Make three integer variables ‘price’ = node[0], ‘current’ = node[1] and ‘stop’ = node[2], where ‘price’ will store the cost of the ticket from source to destination, ‘current’ will store the current node and ‘stop’ will store the number of stops.
- If current = destination, return price.
- If stop > 0, i.e the number of stops is greater than 0.
- Now run a loop to traverse adjList[current] and then push all the adjacent nodes of the current vertex{price + next.second, next.first, stop-1} into the minHeap, update price by adding the cost of current edge to price and also decrease the number of stops by 1.
- Return -1, when none of the above conditions is met.
We can see that for a node, we are finding the ticket price from that node to the destination multiple times, in order to avoid repeated calculations, we store the result in our ‘dp’ matrix.
Algorithm:
- Create a 2D matrix ‘dp’ with K+2 rows and N columns, where dp[i][j] will represent the cheapest price to reach station ‘j’ with maximum ‘i’ stops.
- Initialise ‘dp’ with an infinite value(INT_MAX).
- Update dp[0][source]=0.
- Run a loop(loop variable i) from 1 till K+1.
- Update dp[i][source] = 0, since the price at the source station is 0.
- Now run a loop to traverse the input ‘trains’ array, assume that the current train goes from station ‘a’ to station ‘b’ with cost ‘c’, then update dp[i][b] = min(dp[i][b], dp[i-1][a] + c) to get the minimum price to reach the destination station. This means that our price will be the minimum of:
- The lowest price to reach the destination with utmost i stops or
- The lowest price to reach the destination with i-1 stops, the sum of price from the starting point + price of the train.
- If dp[K+1][destination] >= INT_MAX, then there no such route exists, hence return ‘-1’, else return dp[K+1][destination].