SDE - Intern

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.

You are present at point ‘A’ which is the top-left cell of an M X N matrix, your destination is point ‘B’, which is the bottom-right cell of the same matrix. Your task is to find the total number of unique paths from point ‘A’ to point ‘B’.In other words, you will be given the dimensions of the matrix as integers ‘M’ and ‘N’, your task is to find the total number of unique paths from the cell MATRIX[0][0] to MATRIX['M' - 1]['N' - 1].

To traverse in the matrix, you can either move Right or Down at each step. For example in a given point MATRIX[i] [j], you can move to either MATRIX[i + 1][j] or MATRIX[i][j + 1].