Minimum Journey Cost To Reach Destination Within Time
A country has n cities numbered from 0 to n - 1. The cities are connected by bidirectional roads. Each road is represented by a string in the format "source,destination,time".
Every visit to a city requires paying that city's passing fee, including visits to the starting city and destination city. A city may be visited more than once, and its fee must be paid for every visit.
Starting from city 0, find the minimum total passing fee required to reach city n - 1 without taking more than maxTime minutes. Return -1 if no valid journey exists.
Multiple roads with different travel times may connect the same pair of cities. No road connects a city to itself.
Method Signature
int minimumJourneyCost(int maxTime, List<String> roads, List<Integer> passingFees)
Parameters
maxTime is the maximum number of minutes allowed for the complete journey.roads contains bidirectional roads. Each string has the format "source,destination,time".n = passingFees.size().
passingFees contains the passing fee for every city, where passingFees.get(i) is the fee for city i.
Return Value
Return the minimum total passing fee for a journey from city 0 to city n - 1 that takes at most maxTime minutes. Return -1 when the destination cannot be reached within the time limit.
Constraints
1 <= maxTime <= 1,000n == passingFees.size()2 <= n <= 1,000n - 1 <= roads.size() <= 1,000- Every entry in
roads has the format "source,destination,time".
0 <= source < n0 <= destination < nsource != destination1 <= time <= 1,0001 <= passingFees.get(i) <= 1,000- All cities are connected by the road network.
- Multiple roads may connect the same pair of cities.
Examples
Example 1
minimumJourneyCost(maxTime = 8, roads = List.of("0,1,3", "1,3,3", "0,2,2", "2,3,7", "1,2,1"), passingFees = List.of(4, 2, 10, 3))
Output: 9
The journey 0 -> 1 -> 3 takes 6 minutes and costs 4 + 2 + 3 = 9.
Example 2
minimumJourneyCost(maxTime = 6, roads = List.of("0,1,1", "1,3,1", "0,2,4", "2,3,2"), passingFees = List.of(2, 100, 3, 4))
Output: 9
The journey 0 -> 2 -> 3 takes exactly 6 minutes and costs 2 + 3 + 4 = 9. The faster journey through city 1 costs more.
Example 3
minimumJourneyCost(maxTime = 4, roads = List.of("0,1,3", "1,2,2", "0,2,8"), passingFees = List.of(5, 6, 2))
Output: -1
Every journey from city 0 to city 2 requires more than 4 minutes.