LeetCode Solutions Blog

Minimum Cost of a Path With Special Roads

Number: 2686

Difficulty: Medium

Paid? No

Problem Description

Given a starting point and a target point in a 2D space, you can travel between any two positions using Manhattan distance as the cost. Additionally, you are given several one-directional special roads that connect one point to another at a fixed cost. The task is to find the minimum cost required to travel from the starting point to the target point, making use of the special roads when beneficial.

Key Insights

The problem can be modeled as finding the shortest path in an implicit graph where nodes are key coordinates: the start point, the target point, and the endpoints of every special road.
From any node, you can move directly to any other node with the cost being their Manhattan distance.
Special roads are directed edges that offer a fixed cost regardless of the Manhattan distance.
A typical approach is to use Dijkstra's algorithm with a priority queue to efficiently compute the minimum cost path.

Space and Time Complexity

Time Complexity: O(n^2) where n is the number of nodes (which is at most 2 + 2 * (number of special roads)). Given specialRoads.length <= 200, n is roughly <= 402. Space Complexity: O(n^2) in the worst case for storing the graph edges (or O(n) if computing edge cost on the fly) plus O(n) for the priority queue and distance array.

Solution

We start by constructing a list of nodes that includes the start point, the target point, and both the start and end points of each special road. Every pair of nodes is connected by an edge whose cost is the Manhattan distance between them (to simulate direct travel). Additionally, for each special road, add a directed edge from its start point to its end point with the provided special cost.

We then apply Dijkstra's algorithm to compute the minimum cost to reach the target node from the start node. Using a priority queue helps in efficiently choosing the next node to process, and we update the minimum cost of reaching adjacent nodes considering both direct Manhattan moves and special road transitions.

Code Solutions

import heapq

def minimumCost(start, target, specialRoads):
    # Create list of unique nodes: start, target, and both endpoints of each special road.
    nodes = [tuple(start), tuple(target)]
    for road in specialRoads:
        # Append special road start and end points.
        r_start = (road[0], road[1])
        r_end = (road[2], road[3])
        nodes.append(r_start)
        nodes.append(r_end)
    
    # Remove duplicates while preserving order.
    seen = set()
    unique_nodes = []
    for node in nodes:
        if node not in seen:
            seen.add(node)
            unique_nodes.append(node)
    
    n = len(unique_nodes)
    
    # Precompute Manhattan distance between two points.
    def manhattan(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])
    
    # Build graph edges:
    # Graph: for any two nodes, an edge with Manhattan cost.
    # Additionally, for each special road, add a directed edge with its special cost.
    graph = {i: [] for i in range(n)}
    # Compute complete graph edges for direct travel.
    for i in range(n):
        for j in range(n):
            if i != j:
                cost = manhattan(unique_nodes[i], unique_nodes[j])
                graph[i].append((j, cost))
    
    # Map each special road start and end to indices.
    node_idx = {node: idx for idx, node in enumerate(unique_nodes)}
    for road in specialRoads:
        s = (road[0], road[1])
        e = (road[2], road[3])
        special_cost = road[4]
        if s in node_idx and e in node_idx:
            u = node_idx[s]
            v = node_idx[e]
            # Add a directed special edge; note, it might be beneficial to override if the special cost is lower.
            graph[u].append((v, special_cost))
    
    # Dijkstra's algorithm.
    start_idx = node_idx[tuple(start)]
    target_idx = node_idx[tuple(target)]
    dist = [float('inf')] * n
    dist[start_idx] = 0
    heap = [(0, start_idx)]
    
    while heap:
        current_cost, u = heapq.heappop(heap)
        if current_cost > dist[u]:
            continue
        if u == target_idx:
            return current_cost
        for v, weight in graph[u]:
            new_cost = current_cost + weight
            if new_cost < dist[v]:
                dist[v] = new_cost
                heapq.heappush(heap, (new_cost, v))
    return dist[target_idx]

# Example test runs
print(minimumCost([1,1], [4,5], [[1,2,3,3,2],[3,4,4,5,1]]))  # Expected output: 5
print(minimumCost([3,2], [5,7], [[5,7,3,2,1],[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]))  # Expected: 7
print(minimumCost([1,1], [10,4], [[4,2,1,1,3],[1,2,7,4,4],[10,3,6,1,2],[6,1,1,2,3]]))  # Expected: 8