Saving Money Problem Statement
Ninja is adventurous and loves traveling while being mindful of his expenses. Given a set of 'N' stations connected by 'M' trains, each train starting from station 'A' and reaching station 'B' at a cost of 'P', your task is to determine the cheapest fare from a specified 'source' station to a 'destination' station, with a maximum of 'K' stops along the way. If no such route is available, return '-1'.
Input:
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers N and M, indicating the number of stations and the number of trains, respectively.
The next M lines of each test case consist of three space-separated integers representing the source station, destination station, and the ticket price for traveling between them.
The final line of each test case includes three space-separated integers: the source station, the destination station, and 'K', the maximum allowable stops.
Output:
For each test case, output an integer P, representing the cheapest price from 'source' to 'destination' with up to 'K' stops. If no such route exists, print '-1'.
Each test case's result is outputted on a new line.
Example:
Example of input and output is not provided. Please refer to the statement and constraints for implementation.
Constraints:
- 1 <= T <= 5
- 1 <= N <= 100
- 0 <= M <= N*(N-1)/2
- 0 <= K <= N - 1
Note:
You do not need to print anything, as the output process is managed. Your task is to implement the function logic to solve the problem.
Given a set of stations connected by trains, find the cheapest fare from a source to a destination with a maximum number of stops allowed.
Iterate through all possible routes with up to 'K' stops using...read more
Top Amazon Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Top HR questions asked in Amazon Software Developer Intern
Reviews
Interviews
Salaries
Users/Month