Find the minimum cost to reach destination using a train

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
5 upvotes
Asked in companies
GrowwDeutsche BankAmazon

Problem statement

There are ‘N’ stations on the route of a train. The train goes from station 0 to ‘N’ - 1. The ticket cost for all pairs of stations (i, j) is given where ‘j’ is greater than ‘i’. Your task is to find the minimum cost to reach the Nth station.

Note:

Cost of entries where j < i  will be represented as INT_MAX VALUE which is 10000 in the price matrix.
Example: 
If ‘N’ = 3

'PRICE[3][3]' = {{0, 15, 80,},
               {INF, 0, 40},
               {INF, INF, 0}};

First, go from 1st station to 2nd at 15 costs, then go from 2nd to 3rd at 40. 15 + 40 = 55 is the total cost.It is cheaper than going directly from station 1 to station 3 as it would have cost 80.

The output will be 55.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer 'T' denoting the number of test cases. 

The first line of each test case contains a single integer 'N', Where ‘N’ is the number of rows and columns in the ‘PRICE’ matrix.

The next ‘N’ lines is as follows: Each line contains ‘N’ space-separated integers representing the cost of pairs (i,j) where ‘i’ and ‘j’ are indices of the matrix ‘PRICE’.
Output format : 
For each test case, return the minimum price that will have to be paid such that the train reaches from 1st to 'N'th station.

Print the output for each test case in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 1000

Time Limit: 1 sec
Sample Input 1 :
2
3
0 15 80
10000 0 40
10000 10000 0
2
0 2
10000 0
Sample Output 1 :
55
2
Explanation of the Sample Output 1:
In test case 1, First, go from 1st station to 2nd at 15 costs then go from 2nd to 3rd at 40 cost. 15 + 40 = 55 is the total cost.

In test case 2, Go from 1st to 2nd station at total cost 2.

Sample Input 2 :

2
2
0 5
10000 0
3
0 15 8
10000 0 40
10000 10000 0

Sample Output 2 :

5
8
Explanation of the Sample Output 2:
In test case 1, Go from 1st to 2nd station at total cost 2.   

In test case 2, Go directly from 1st to 3rd station at total cost 8.
Hint

Can we find the minimum cost of travel from one station to another?

Approaches (2)
Floyd Warshall Algorithm

The idea is to calculate the minimum price between all pair of stations using Floyd Warshall Algorithm:

 

  • Pick all vertices and update all minimum-cost-paths that include the selected station as an intermediate station in the minimum-cost-path.
  • When we pick vertex number ‘K’ as an intermediate station, we already have considered vertices {0, 1, 2, .. ‘K’ - 1} as intermediate vertices. For every pair ('i', ‘j’) of the source station and destination station, respectively, there are two possible cases.
    • ‘K’ is not an intermediate station in the minimum-cost-path from ‘i’ to ‘j’. We keep the value of ‘DIST[i][j]’ as it is.
    • ‘K’ is an intermediate station in the minimum-cost-path from i to j. We update the value of ‘DIST[i][j]' as ‘DIST[i][K]' + ‘DIST[K][j]' if ‘DIST[i][j]' > ‘DIST[i][K]' + ‘DIST[K][j]'.
  • Then return the ‘DIST[0]['N' - 1]' because that stores the minimum cost to travel from source to destination.
Time Complexity

O(N ^ 3), Where ‘N’ is the number of rows and columns of the matrix.

 

Since we have to traverse the 2-D matrix completely N times. Thus, the time complexity will be O(N ^ 3).

Space Complexity

O(N ^ 2), Where ‘N’ is the number of rows and columns of the matrix.

 

Since we are using an extra 2-D matrix to keep track of the minimum-cost-path for each station. Thus the space complexity will be O(N ^ 2).

Code Solution
(100% EXP penalty)
Find the minimum cost to reach destination using a train
Full screen
Console