Minimum Round Trip Lengths
Microsoft● MediumOAProblem statement
A traveling salesperson lives in a country that has road_nodes houses and m roads. The j-th road runs from house x[j] to house y[j] and has a length of t[j]. The roads are directional, meaning it is not possible to travel from house y[j] to house x[j] using the same road.
For each house x, where 1 <= x <= road_nodes, find the minimum length of a journey that starts and ends at house x. If no such path exists for a particular house x, return 0 for that house.
Note:
- There are no multiple roads between
2houses. - There can be a road that starts and ends at the same house.
- All houses may or may not be connected.
Function
minimumRoundTripLengths(roads_nodes: int, m: int, roads_from: int[], roads_to: int[], roads_weight: int[]) → int[]Examples
Example 1
roads_nodes = 4m = 4roads_from = [1, 2, 3, 4]roads_to = [2, 3, 1, 3]roads_weight = [14, 23, 23, 30]return = [60, 60, 60, 0]The visible roads are 1 -> 2 with length 14, 2 -> 3 with length 23, 3 -> 1 with length 23, and 4 -> 3 with length 30.
Houses 1, 2, and 3 can each travel around the directed cycle 1 -> 2 -> 3 -> 1, whose total length is 14 + 23 + 23 = 60. House 4 has no journey that returns to house 4, so its value is 0.