Minimum Travel Cost Problem
You are given a country called 'Ninjaland' with 'N' states, numbered from 1 to 'N'. These states are connected by 'M' bidirectional roads, each with a specified travel cost. The aim is to select exactly 'N' - 1 roads so that a tourist bus can travel to every state at least once, minimizing the total travel cost.
Example:
Input:
Consider a country with 4 states (1 to 4) and 5 bidirectional roads:
1 --- 2, cost = 8
2 --- 3, cost = 6
3 --- 4, cost = 5
1 --- 4, cost = 2
1 --- 3, cost = 4
Output:
The optimal roads can be selected as follows:
1 --- 4, cost = 2
1 --- 3, cost = 4
2 --- 3, cost = 6
Total minimum travel cost = 12.
Constraints:
1 ≤ 'T' ≤ 10
(Number of test cases)1 ≤ 'N' ≤ 1000
(Number of states)'N' - 1 ≤ 'M' ≤ 2000
(Number of roads)1 ≤ 'C' ≤ 106
(Cost of roads)- Time limit: 1 sec
Input:
The first line contains an integer 'T'.
Each test case consists of:
- An integer 'N' and 'M'.
- 'M' lines, each containing three integers 'A', 'B', and 'C'.
Output:
For each test case, print 'N' - 1 lines, each containing three integers 'A', 'B', and 'C' indicating the chosen roads with their costs.
Note:
You do not need to manually print anything as it is handled by the system. Just implement the function to find the minimum cost selection of roads.
Find the minimum cost selection of roads to travel to every state in a country.
Create a graph representation of the states and roads with their costs.
Use a minimum spanning tree algorithm like Kruskal...read more
Top JPMorgan Chase & Co. Software Developer interview questions & answers
Popular interview questions of Software Developer
Top HR questions asked in JPMorgan Chase & Co. Software Developer
Reviews
Interviews
Salaries
Users/Month