Last Updated: 2 Mar, 2021

Find the minimum cost to reach destination using a train

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

The idea is based on the fact that the given input matrix is a Directed Acyclic Graph (DAG) because we can go from a smaller station to another and not the other way around hence DAG. The shortest path in DAG can be calculated using topological sorting.

Calculate min cost for station 1, then for station 2, etc. These costs are stored in an array ‘DIST[0…'N' - 1]'.
The min cost for station 0 is 0, i.e., ‘DIST[0]' = 0.
The min cost for station 1 is cost[0][1], i.e., ‘DIST[1]' = cost[0][1]
The min cost for station 2 is the minimum of the following two.
- ‘DIST[0]' + cost[0][2]
- ‘DIST[1]' + cost[1][2]
The min cost for station 3 is the minimum of the following three.
- ‘DIST[0]' + cost[0][3]
- ‘DIST[1]' + cost[1][3]
- ‘DIST[2]' + cost[2][3]
Similarly, ‘DIST[4]', ‘DIST[5]', … ‘DIST['N' - 1]' are calculated.
Hence after all iterations, our answer will get stored at the ‘N’th block, therefore, return it.

Solve now