323. Cheapest Journey Between Cities

Cheapest Journey Between Cities

There are n cities connected by bidirectional roads. Each road has a fixed travel time, and every city has a local taxi service that charges a different amount per minute.

You begin by hiring a taxi in the starting city. The same taxi may travel through multiple cities. After reaching a city, you may switch to that city's taxi only when its per-minute rate is lower than the rate of your current taxi.

Find the minimum total cost required to travel from startCity to destinationCity. Return -1 if the destination cannot be reached.

Method Signature

long minimumJourneyCost(List<Integer> taxiRates, List<String> roads, int startCity, int destinationCity)

Parameters

n = taxiRates.size() is the number of cities.
taxiRates.get(i) is the charge per minute of a taxi hired in City i + 1.
Each string in roads has the format "city1,city2,travelTime".
A road string represents a bidirectional road between city1 and city2 that takes travelTime minutes.
startCity is the city where the journey begins.
destinationCity is the city where the journey ends.

Taxi Rules

You must hire the local taxi available in startCity.
A taxi can travel through any number of connected cities.
On reaching another city, you may keep your current taxi or switch to the local taxi if its rate is lower.
The cost of traveling across a road is the road's travel time multiplied by the rate of the taxi currently being used.
The chosen journey does not have to use the route with the smallest total travel time.

Return Value

Return the minimum possible total journey cost.
Return 0 when startCity and destinationCity are the same.
Return -1 when destinationCity cannot be reached from startCity.

Constraints

1 ≤ taxiRates.size() ≤ 100,000
1 ≤ roads.size() ≤ 200,000
1 ≤ taxiRates.get(i) ≤ 1,000,000
1 ≤ city1, city2 ≤ taxiRates.size()
city1 != city2
1 ≤ travelTime ≤ 1,000,000
1 ≤ startCity, destinationCity ≤ taxiRates.size()
Every road string contains exactly three comma-separated positive integers.
The minimum journey cost, when a route exists, fits in a signed long.

Examples

Example 1

 minimumJourneyCost(taxiRates = [8, 5, 10, 2, 7], roads = ["1,2,3", "2,5,5", "2,3,1", "3,4,2", "4,5,4"], startCity = 1, destinationCity = 5)

Output: 47

The cheapest journey is 1 → 2 → 3 → 4 → 5. The taxi from City 1 costs 3 × 8 = 24 to reach City 2. After switching to City 2's taxi, reaching City 4 costs (1 + 2) × 5 = 15. Switching to City 4's taxi makes the final road cost 4 × 2 = 8. The total is 24 + 15 + 8 = 47.

Example 2

minimumJourneyCost(taxiRates = [6, 8, 1], roads = ["1,2,5", "1,3,2", "3,2,5"], startCity = 1, destinationCity = 2)

Output: 17

Traveling directly from City 1 to City 2 costs 5 × 6 = 30. Going through City 3 costs 2 × 6 = 12, after which switching to City 3's taxi makes the remaining road cost 5 × 1 = 5. Therefore, the minimum total cost is 17.

Example 3

minimumJourneyCost(taxiRates = [4, 2, 7, 3], roads = ["1,2,6", "3,4,2"], startCity = 1, destinationCity = 4)

Output: -1

Cities 1 and 4 belong to separate connected groups, so the destination cannot be reached.

Example 4

minimumJourneyCost(taxiRates = [9, 3, 5], roads = ["1,2,4", "2,3,7"], startCity = 2, destinationCity = 2)

Output: 0

The journey starts and ends in City 2, so no road travel is required.