Company: MakeMyTrip
Difficulty: medium
Trip Planner Max score: 50.00 You are planning a bus journey across a network of towns. There are n towns connected by several bus routes. You are given an array routes where routes[i] = [startTown, endTown, fare] indicates that there is a bus route from town startTown to town endTown with a ticket fare of fare. You want to travel from your hometown to visit a friend in another town. The problem is, you want to keep your expenses as low as possible. However, you don\'t mind making a few stops along the way to save some money. Additionally, you don\'t want your journey to be too tedious, so you limit the number of stops you can make to a maximum of maxStops. Input Format First line contains 5 space-separated integers: Number of towns (n) Source town Destination town Maximum stops allowed Number of routes Following lines contain the bus routes, each with 3 space-separated integers: startTown endTown fare Output Format Print a single integer representing the minimum fare required to reach