Practice/Google/Leetcode 2662. Minimum Cost of a Path With Special Roads

Leetcode 2662. Minimum Cost of a Path With Special Roads

CodingOptional

Problem

You are planning a trip on an infinite 2D grid where you start at a given position and want to reach a target position. Moving from any point to any other point normally costs the Manhattan distance between them (the sum of absolute differences in x and y coordinates).

However, there are special express routes available. Each express route is a directed shortcut that goes from one specific point to another specific point for a fixed cost. These express routes can be used any number of times.

Your task is to determine the minimum cost to travel from the start position to the target position, potentially using any combination of normal movement and express routes.

Requirements

1. Calculate the minimum cost path from start to target
2. Consider both direct Manhattan distance travel and express routes
3. Express routes are directional (can only be used in the specified direction)
4. Express routes can be used multiple times
5. You can move to any point on the grid at any time using Manhattan distance

Constraints

• -10^6 <= start[0], start[1], target[0], target[1] <= 10^6
• 0 <= expressRoutes.length <= 200
• expressRoutes[i].length == 5
• expressRoutes[i] = [x1, y1, x2, y2, cost] represents a route from (x1, y1) to (x2, y2) with given cost
• 1 <= cost <= 10^6
• Time complexity target: O(n² log n) where n is the number of unique points
• Space complexity target: O(n²)

Examples

Example 1:

Input: start = [0, 0], target = [5, 5], expressRoutes = [[0, 0, 5, 5, 3]] Output: 3 Explanation: The direct Manhattan distance from (0,0) to (5,5) is |5-0| + |5-0| = 10. However, there's an express route from (0,0) to (5,5) that costs only 3, so we take it.

Example 2:

Input: start = [0, 0], target = [10, 10], expressRoutes = [[0, 0, 5, 5, 3], [5, 5, 10, 10, 4]] Output: 7 Explanation: We can chain express routes: take the first from (0,0) to (5,5) for cost 3, then take the second from (5,5) to (10,10) for cost 4. Total cost is 7, which is much better than the direct Manhattan distance of 20.

Example 3:

Input: start = [1, 1], target = [3, 3], expressRoutes = [[1, 1, 3, 3, 10]] Output: 4 Explanation: The express route costs 10, but walking directly costs |3-1| + |3-1| = 4. We ignore the expensive express route and walk directly.