Find the Minimum Cost to Reach Destination via Train

Given 'N' stations on a train route, where the train travels from station 0 to 'N'-1, determine the minimum cost to reach the final station using given ticket costs for each pair of stations (i, j) where j > i.

Input:

The first line contains an integer 'T', the number of test cases.
The first line of each test case contains a single integer 'N', indicating the size of the 'PRICE' matrix, which is N x N.
The following N lines each contain 'N' space-separated integers, representing the costs from station i to station j in the 'PRICE' matrix.

Output:

For each test case, output the minimum cost to travel from station 1 to station 'N'. Output each result on a new line.

Example:

If N = 3
PRICE[3][3] = [[0, 15, 80],
[INF, 0, 40],
[INF, INF, 0]];
The minimum cost is 55, achieved by traveling from station 1 to 2 with cost 15, then from station 2 to 3 with cost 40.

Constraints:

  • 1 <= T <= 100
  • 1 <= N <= 1000

Note:

Cost entries for j < i are represented by INT_MAX, which is 10000 in the matrix. You don't need to print anything - just implement and return the result.
AnswerBot
8d

Find the minimum cost to reach the destination via train using given ticket costs for each pair of stations.

  • Create a 2D array to store the costs from each station to the final destination.

  • Use dynamic ...read more

Help your peers!
Add answer anonymously...
Deutsche Bank Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter