# Minimum Cost of a Path With Special Roads
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-cost-of-a-path-with-special-roads)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-of-a-path-with-special-roads
**Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Array, Heap (Priority Queue), Graph
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung)
---
## Problem
You are given an array `start` where `start = [startX, startY]` represents your initial position `(startX, startY)` in a 2D space. You are also given the array `target` where `target = [targetX, targetY]` represents your target position `(targetX, targetY)`.

The **cost** of going from a position `(x1, y1)` to any other position in the space `(x2, y2)` is `|x2 - x1| + |y2 - y1|`.

There are also some **special roads**. You are given a 2D array `specialRoads` where `specialRoads[i] = [x1i, y1i, x2i, y2i, costi]` indicates that the `ith` special road goes in **one direction** from `(x1i, y1i)` to `(x2i, y2i)` with a cost equal to `costi`. You can use each special road any number of times.

Return the **minimum** cost required to go from `(startX, startY)` to `(targetX, targetY)`.

**Example 1:**

**Input:** start = \[1,1\], target = \[4,5\], specialRoads = \[\[1,2,3,3,2\],\[3,4,4,5,1\]\]

**Output:** 5

**Explanation:**

1. (1,1) to (1,2) with a cost of |1 - 1| + |2 - 1| = 1.
2. (1,2) to (3,3). Use `specialRoads[0]` with the cost 2.
3. (3,3) to (3,4) with a cost of |3 - 3| + |4 - 3| = 1.
4. (3,4) to (4,5). Use `specialRoads[1]` with the cost 1.

So the total cost is 1 + 2 + 1 + 1 = 5.

**Example 2:**

**Input:** start = \[3,2\], target = \[5,7\], specialRoads = \[\[5,7,3,2,1\],\[3,2,3,4,4\],\[3,3,5,5,5\],\[3,4,5,6,6\]\]

**Output:** 7

**Explanation:**

It is optimal not to use any special edges and go directly from the starting to the ending position with a cost |5 - 3| + |7 - 2| = 7.

Note that the `specialRoads[0]` is directed from (5,7) to (3,2).

**Example 3:**

**Input:** start = \[1,1\], target = \[10,4\], specialRoads = \[\[4,2,1,1,3\],\[1,2,7,4,4\],\[10,3,6,1,2\],\[6,1,1,2,3\]\]

**Output:** 8

**Explanation:**

1. (1,1) to (1,2) with a cost of |1 - 1| + |2 - 1| = 1.
2. (1,2) to (7,4). Use `specialRoads[1]` with the cost 4.
3. (7,4) to (10,4) with a cost of |10 - 7| + |4 - 4| = 3.

**Constraints:**

* `start.length == target.length == 2`
* `1 <= startX <= targetX <= 105`
* `1 <= startY <= targetY <= 105`
* `1 <= specialRoads.length <= 200`
* `specialRoads[i].length == 5`
* `startX <= x1i, x2i <= targetX`
* `startY <= y1i, y2i <= targetY`
* `1 <= costi <= 105`

# Approaches
## Dijkstra on Explicit Graph of All Key Points
This approach models the problem as a classic shortest path problem on a graph. The nodes of the graph are the `start` point, `target` point, and all the start and end points of the special roads. The edges represent the cost of travel between these points. By constructing this graph explicitly and then running Dijkstra's algorithm, we can find the minimum cost from the `start` to the `target`.
**Time:** O(M^2 log M), where M is the number of unique key points (at most 2N+2, where N is the number of special roads). Building the graph takes O(M^2) and Dijkstra's algorithm on a dense graph with a priority queue takes O(E log M) = O(M^2 log M). · **Space:** O(M^2), where M is the number of unique key points (at most 2N+2). This is for storing the adjacency list of the dense graph.
**Pros:** Conceptually straightforward application of a standard algorithm.; Guaranteed to find the optimal solution.
**Cons:** Higher space complexity due to storing a dense graph.; Higher time complexity compared to the optimized approach.; Implementation can be more complex due to the need to correctly merge Manhattan distance costs and special road costs into a single graph structure.
### Explanation
First, we identify all critical points in the 2D space. These are the `start` point, the `target` point, and all start and end coordinates of the `specialRoads`. Let's say there are `M` unique such points. These points will be the vertices of our graph.

We then construct a complete directed graph where the weight of the edge from any point `u` to any point `v` is initially the Manhattan distance `|u.x - v.x| + |u.y - v.y|`. The special roads introduce alternative, potentially cheaper, paths. For each special road from a point `u` to a point `v` with cost `c`, we update the weight of the directed edge from `u` to `v` to be the minimum of its current weight and `c`.

After constructing this graph with `M` vertices and `O(M^2)` edges, the problem is reduced to finding the shortest path from the `start` node to the `target` node. Dijkstra's algorithm is perfectly suited for this since all edge weights are non-negative. The final answer is the shortest distance computed for the `target` node.

```java
import java.util.*;

class Solution {
    private long manhattanDist(int[] p1, int[] p2) {
        return Math.abs((long)p1[0] - p2[0]) + Math.abs((long)p1[1] - p2[1]);
    }

    public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
        List<int[]> points = new ArrayList<>();
        Map<Long, Integer> pointToIndex = new HashMap<>();

        java.util.function.Function<int[], Integer> addPoint = (p) -> {
            long key = (long)p[0] * 100001L + p[1];
            if (!pointToIndex.containsKey(key)) {
                pointToIndex.put(key, points.size());
                points.add(p);
            }
            return pointToIndex.get(key);
        };

        addPoint.apply(start);
        addPoint.apply(target);
        for (int[] road : specialRoads) {
            addPoint.apply(new int[]{road[0], road[1]});
            addPoint.apply(new int[]{road[2], road[3]});
        }

        int n = points.size();
        List<List<long[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        Map<Long, Long> specialEdgeCosts = new HashMap<>();
        for (int[] road : specialRoads) {
            long uKey = (long)road[0] * 100001L + road[1];
            long vKey = (long)road[2] * 100001L + road[3];
            long edgeKey = (uKey << 32) | vKey;
            specialEdgeCosts.put(edgeKey, Math.min(specialEdgeCosts.getOrDefault(edgeKey, Long.MAX_VALUE), (long)road[4]));
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                long p1Key = (long)points.get(i)[0] * 100001L + points.get(i)[1];
                long p2Key = (long)points.get(j)[0] * 100001L + points.get(j)[1];
                long edgeKey = (p1Key << 32) | p2Key;
                
                long cost = manhattanDist(points.get(i), points.get(j));
                cost = Math.min(cost, specialEdgeCosts.getOrDefault(edgeKey, Long.MAX_VALUE));
                adj.get(i).add(new long[]{j, cost});
            }
        }

        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        
        int startIdx = addPoint.apply(start);
        int targetIdx = addPoint.apply(target);
        
        dist[startIdx] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{0, startIdx});

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long d = current[0];
            int u = (int) current[1];

            if (d > dist[u]) continue;
            if (u == targetIdx) return (int) d;

            for (long[] edge : adj.get(u)) {
                int v = (int) edge[0];
                long weight = edge[1];
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }
        
        return (int) dist[targetIdx];
    }
}
```
### Algorithm
- Collect all unique key points: `start`, `target`, and all start/end points of `specialRoads`. Let there be `M` such points.
- Create a mapping from each point to an index from `0` to `M-1`.
- Build an adjacency list representing a complete graph. For every pair of points `u` and `v`, the edge weight is the minimum of the Manhattan distance and the cost of a special road if one exists between them.
- This results in a graph with `M` nodes and `O(M^2)` edges.
- Apply Dijkstra's algorithm on this graph, starting from the `start` node's index.
- The result is the computed shortest distance to the `target` node's index.

## Optimized Dijkstra on Special Road Endpoints
This is a more refined application of Dijkstra's algorithm that leverages the specific structure of the problem. Instead of building a graph of all key points, we focus on finding the minimum cost to reach only the destination points of the special roads. This is because any optimal path will consist of segments of normal travel connecting the `start`, `target`, and special road endpoints. This approach efficiently calculates the costs to these crucial 'junction' points.
**Time:** O(N^2), where N is the number of special roads. In the worst case, Dijkstra's algorithm will process each of the N destination points. From each point, it iterates through all N special roads to find subsequent paths. With a priority queue, this leads to a complexity around O(N^2). · **Space:** O(N), where N is the number of special roads. This is for the distance map and the priority queue, which store information for at most N unique destination points.
**Pros:** Very efficient in both time and space.; Reduces the number of nodes in the Dijkstra search compared to the explicit graph approach, potentially leading to better performance.; The implementation is clean and directly models the decision-making process at each step.
**Cons:** The logic can be slightly less intuitive than building a standard graph, as it's tailored to the problem's structure.
### Explanation
The core idea is to use Dijkstra's algorithm to find the shortest path from the `start` point to each special road's destination point. The overall minimum cost will be the minimum of the direct path from `start` to `target` and paths that go through one or more special roads.

We maintain a `dist` map to store the minimum cost found so far to reach each special road's destination. A priority queue stores `(cost, point)` tuples, ordered by cost.

1.  The initial best answer is the Manhattan distance from `start` to `target`.
2.  We begin by considering paths from `start` that use exactly one special road. For each special road, we calculate `cost = manhattan(start, road_start) + road_cost`. We update the `dist` map for `road_end` and push `{cost, road_end}` to the priority queue.
3.  Then, we run Dijkstra's. We repeatedly extract the point `u` with the minimum cost from the priority queue.
4.  From `u`, we can either go directly to the `target`. We update our overall best answer with `cost[u] + manhattan(u, target)`.
5.  Or, from `u`, we can travel to the start of any other special road `j`, take that road, and arrive at its destination. The cost for this new path is `cost[u] + manhattan(u, road_start_j) + road_cost_j`. If this path is shorter, we update the distance to `road_end_j` and add it to the priority queue.

This process continues until the priority queue is empty, guaranteeing we have found the minimum costs to all reachable special road destinations and, by extension, the minimum cost to the target.

```java
import java.util.*;

class Solution {
    private long manhattanDist(int[] p1, int[] p2) {
        return Math.abs((long)p1[0] - p2[0]) + Math.abs((long)p1[1] - p2[1]);
    }

    public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
        long minCost = manhattanDist(start, target);

        Map<Long, Long> dist = new HashMap<>();
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));

        for (int[] road : specialRoads) {
            long startToRoadStartCost = manhattanDist(start, new int[]{road[0], road[1]});
            long totalCost = startToRoadStartCost + road[4];
            long roadDestKey = (long)road[2] * 100001L + road[3];

            if (totalCost < dist.getOrDefault(roadDestKey, Long.MAX_VALUE)) {
                dist.put(roadDestKey, totalCost);
                pq.offer(new long[]{totalCost, road[2], road[3]});
            }
        }

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long cost = current[0];
            int[] u = new int[]{(int)current[1], (int)current[2]};
            long uKey = (long)u[0] * 100001L + u[1];

            if (cost > dist.getOrDefault(uKey, Long.MAX_VALUE)) {
                continue;
            }

            minCost = Math.min(minCost, cost + manhattanDist(u, target));

            for (int[] road : specialRoads) {
                long uToRoadStartCost = manhattanDist(u, new int[]{road[0], road[1]});
                long totalCost = cost + uToRoadStartCost + road[4];
                long roadDestKey = (long)road[2] * 100001L + road[3];

                if (totalCost < dist.getOrDefault(roadDestKey, Long.MAX_VALUE)) {
                    dist.put(roadDestKey, totalCost);
                    pq.offer(new long[]{totalCost, road[2], road[3]});
                }
            }
        }

        return (int) minCost;
    }
}
```
### Algorithm
- Initialize the minimum cost to be the direct Manhattan distance from `start` to `target`.
- Use a priority queue for Dijkstra's algorithm to find the minimum cost to reach the destination point of each special road.
- The states in the priority queue are `(cost, x, y)`, representing the minimum cost to reach point `(x, y)`.
- Initially, populate the priority queue by calculating the cost from `start` to each special road's destination (i.e., `cost(start -> road_start) + road_cost`).
- In the main Dijkstra loop, when visiting a point `u` (which is a destination of a special road):
  - Update the overall minimum cost by considering traveling from `u` to the `target`.
  - For every other special road, calculate the cost of traveling from `u` to its destination and update its minimum cost if a shorter path is found.

# Solutions
### Java

```java
class Solution {
public
  int minimumCost(int[] start, int[] target, int[][] specialRoads) {
    int ans = 1 << 30;
    int n = 1000000;
    PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[0] - b[0]);
    Set<Long> vis = new HashSet<>();
    q.offer(new int[]{0, start[0], start[1]});
    while (!q.isEmpty()) {
      var p = q.poll();
      int x = p[1], y = p[2];
      long k = 1L * x * n + y;
      if (vis.contains(k)) {
        continue;
      }
      vis.add(k);
      int d = p[0];
      ans = Math.min(ans, d + dist(x, y, target[0], target[1]));
      for (var r : specialRoads) {
        int x1 = r[0], y1 = r[1], x2 = r[2], y2 = r[3], cost = r[4];
        q.offer(new int[]{d + dist(x, y, x1, y1) + cost, x2, y2});
      }
    }
    return ans;
  }
private
  int dist(int x1, int y1, int x2, int y2) {
    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumCost(vector<int> &start, vector<int> &target,
                  vector<vector<int>> &specialRoads) {
    auto dist = [](int x1, int y1, int x2, int y2) {
      return abs(x1 - x2) + abs(y1 - y2);
    };
    int ans = 1 << 30;
    int n = 1e6;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
                   greater<tuple<int, int, int>>>
        pq;
    pq.push({0, start[0], start[1]});
    unordered_set<long long> vis;
    while (!pq.empty()) {
      auto [d, x, y] = pq.top();
      pq.pop();
      long long k = 1LL * x * n + y;
      if (vis.count(k)) {
        continue;
      }
      vis.insert(k);
      ans = min(ans, d + dist(x, y, target[0], target[1]));
      for (auto &r : specialRoads) {
        int x1 = r[0], y1 = r[1], x2 = r[2], y2 = r[3], cost = r[4];
        pq.push({d + dist(x, y, x1, y1) + cost, x2, y2});
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int: def dist(x1: int, y1: int, x2: int, y2: int) -> int: return abs(x1 - x2) + abs(y1 - y2) q = [(0, start[0], start[1])] vis = set() ans = inf while q: d, x, y = heappop(q) if (x, y) in vis: continue vis . add((x, y)) ans = min(ans, d + dist(x, y, * target)) for x1, y1, x2, y2, cost in specialRoads: heappush(q, (d + dist(x, y, x1, y1) + cost, x2, y2)) return ans

```