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.

AnswerBot
5d

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

Help your peers!
Add answer anonymously...
JPMorgan Chase & Co. Software Developer 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