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).

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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 <= 10^5
  • 1 <= startY <= targetY <= 10^5
  • 1 <= specialRoads.length <= 200
  • specialRoads[i].length == 5
  • startX <= x1i, x2i <= targetX
  • startY <= y1i, y2i <= targetY
  • 1 <= costi <= 10^5

Solution

Method 1 – Dijkstra’s Algorithm

Intuition

We treat each point (start, target, and all special road endpoints) as a node in a graph. The cost to move between any two points is the Manhattan distance, except for special roads, which have their own cost. Dijkstra’s algorithm finds the shortest path from start to target efficiently.

Approach

  1. Collect all unique points: start, target, and all special road endpoints.
  2. Build edges:
    • For every pair of points, add an edge with cost equal to their Manhattan distance.
    • For each special road, add an edge from its start to its end with the given cost.
  3. Use Dijkstra’s algorithm:
    • Start from the start point.
    • Use a min-heap to always expand the lowest-cost node.
    • Track the minimum cost to reach each point.
    • Stop when reaching the target.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
        using P = pair<int, int>;
        vector<P> pts = { {start[0], start[1]}, {target[0], target[1]} };
        for (auto& r : specialRoads) {
            pts.push_back({r[0], r[1]});
            pts.push_back({r[2], r[3]});
        }
        unordered_map<int, unordered_map<int, int>> dist;
        for (auto& p : pts) dist[p.first][p.second] = INT_MAX;
        dist[start[0]][start[1]] = 0;
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
        pq.push({0, start[0], start[1]});
        while (!pq.empty()) {
            auto [cost, x, y] = pq.top(); pq.pop();
            if (cost > dist[x][y]) continue;
            int direct = abs(x - target[0]) + abs(y - target[1]);
            if (dist[target[0]][target[1]] > cost + direct) {
                dist[target[0]][target[1]] = cost + direct;
                pq.push({cost + direct, target[0], target[1]});
            }
            for (auto& r : specialRoads) {
                int d = abs(x - r[0]) + abs(y - r[1]) + r[4];
                if (dist[r[2]][r[3]] > cost + d) {
                    dist[r[2]][r[3]] = cost + d;
                    pq.push({cost + d, r[2], r[3]});
                }
            }
        }
        return dist[target[0]][target[1]];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func minimumCost(start []int, target []int, specialRoads [][]int) int {
    type pt struct{ x, y int }
    pts := []pt{{start[0], start[1]}, {target[0], target[1]}}
    for _, r := range specialRoads {
        pts = append(pts, pt{r[0], r[1]}, pt{r[2], r[3]})
    }
    dist := map[pt]int{}
    for _, p := range pts { dist[p] = 1<<31 - 1 }
    dist[pt{start[0], start[1]}] = 0
    pq := &heapMin{}; heap.Init(pq)
    heap.Push(pq, node{0, start[0], start[1]})
    for pq.Len() > 0 {
        n := heap.Pop(pq).(node)
        if n.c > dist[pt{n.x, n.y}] { continue }
        direct := abs(n.x-target[0]) + abs(n.y-target[1])
        if dist[pt{target[0], target[1]}] > n.c+direct {
            dist[pt{target[0], target[1]}] = n.c+direct
            heap.Push(pq, node{n.c+direct, target[0], target[1]})
        }
        for _, r := range specialRoads {
            d := abs(n.x-r[0]) + abs(n.y-r[1]) + r[4]
            if dist[pt{r[2], r[3]}] > n.c+d {
                dist[pt{r[2], r[3]}] = n.c+d
                heap.Push(pq, node{n.c+d, r[2], r[3]})
            }
        }
    }
    return dist[pt{target[0], target[1]}]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
    public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
        Set<String> pts = new HashSet<>();
        pts.add(start[0]+","+start[1]);
        pts.add(target[0]+","+target[1]);
        for (int[] r : specialRoads) {
            pts.add(r[0]+","+r[1]);
            pts.add(r[2]+","+r[3]);
        }
        Map<String, Integer> dist = new HashMap<>();
        for (String p : pts) dist.put(p, Integer.MAX_VALUE);
        String s = start[0]+","+start[1];
        dist.put(s, 0);
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
        pq.offer(new int[]{0, start[0], start[1]});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            if (cur[0] > dist.get(cur[1]+","+cur[2])) continue;
            int direct = Math.abs(cur[1]-target[0]) + Math.abs(cur[2]-target[1]);
            String t = target[0]+","+target[1];
            if (dist.get(t) > cur[0]+direct) {
                dist.put(t, cur[0]+direct);
                pq.offer(new int[]{cur[0]+direct, target[0], target[1]});
            }
            for (int[] r : specialRoads) {
                int d = Math.abs(cur[1]-r[0]) + Math.abs(cur[2]-r[1]) + r[4];
                String e = r[2]+","+r[3];
                if (dist.get(e) > cur[0]+d) {
                    dist.put(e, cur[0]+d);
                    pq.offer(new int[]{cur[0]+d, r[2], r[3]});
                }
            }
        }
        return dist.get(target[0]+","+target[1]);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    fun minimumCost(start: IntArray, target: IntArray, specialRoads: Array<IntArray>): Int {
        val pts = mutableSetOf<Pair<Int,Int>>()
        pts.add(Pair(start[0], start[1]))
        pts.add(Pair(target[0], target[1]))
        for (r in specialRoads) {
            pts.add(Pair(r[0], r[1]))
            pts.add(Pair(r[2], r[3]))
        }
        val dist = mutableMapOf<Pair<Int,Int>,Int>()
        for (p in pts) dist[p] = Int.MAX_VALUE
        dist[Pair(start[0], start[1])] = 0
        val pq = PriorityQueue(compareBy<Pair<Int,Int>> { dist[it]!! })
        pq.add(Pair(start[0], start[1]))
        while (pq.isNotEmpty()) {
            val (x, y) = pq.poll()
            val cost = dist[Pair(x, y)]!!
            val direct = Math.abs(x - target[0]) + Math.abs(y - target[1])
            if (dist[Pair(target[0], target[1])]!! > cost + direct) {
                dist[Pair(target[0], target[1])] = cost + direct
                pq.add(Pair(target[0], target[1]))
            }
            for (r in specialRoads) {
                val d = Math.abs(x - r[0]) + Math.abs(y - r[1]) + r[4]
                val e = Pair(r[2], r[3])
                if (dist[e]!! > cost + d) {
                    dist[e] = cost + d
                    pq.add(e)
                }
            }
        }
        return dist[Pair(target[0], target[1])]!!
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def manhattan(a: tuple[int, int], b: tuple[int, int]) -> int:
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

class Solution:
    def minimumCost(self, start: list[int], target: list[int], specialRoads: list[list[int]]) -> int:
        import heapq
        pts = {(start[0], start[1]), (target[0], target[1])}
        for r in specialRoads:
            pts.add((r[0], r[1]))
            pts.add((r[2], r[3]))
        dist = {p: float('inf') for p in pts}
        dist[(start[0], start[1])] = 0
        pq: list[tuple[int, int, int]] = [(0, start[0], start[1])]
        while pq:
            cost, x, y = heapq.heappop(pq)
            if cost > dist[(x, y)]: continue
            direct = abs(x - target[0]) + abs(y - target[1])
            if dist[(target[0], target[1])] > cost + direct:
                dist[(target[0], target[1])] = cost + direct
                heapq.heappush(pq, (cost + direct, target[0], target[1]))
            for r in specialRoads:
                d = abs(x - r[0]) + abs(y - r[1]) + r[4]
                if dist[(r[2], r[3])] > cost + d:
                    dist[(r[2], r[3])] = cost + d
                    heapq.heappush(pq, (cost + d, r[2], r[3]))
        return dist[(target[0], target[1])]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

impl Solution {
    pub fn minimum_cost(start: Vec<i32>, target: Vec<i32>, special_roads: Vec<Vec<i32>>) -> i32 {
        use std::collections::{HashSet, HashMap, BinaryHeap};
        use std::cmp::Reverse;
        let mut pts = HashSet::new();
        pts.insert((start[0], start[1]));
        pts.insert((target[0], target[1]));
        for r in &special_roads {
            pts.insert((r[0], r[1]));
            pts.insert((r[2], r[3]));
        }
        let mut dist = HashMap::new();
        for &p in &pts { dist.insert(p, i32::MAX); }
        dist.insert((start[0], start[1]), 0);
        let mut pq = BinaryHeap::new();
        pq.push(Reverse((0, start[0], start[1])));
        while let Some(Reverse((cost, x, y))) = pq.pop() {
            if cost > dist[&(x, y)] { continue; }
            let direct = (x - target[0]).abs() + (y - target[1]).abs();
            if dist[&(target[0], target[1])] > cost + direct {
                dist.insert((target[0], target[1]), cost + direct);
                pq.push(Reverse((cost + direct, target[0], target[1])));
            }
            for r in &special_roads {
                let d = (x - r[0]).abs() + (y - r[1]).abs() + r[4];
                if dist[&(r[2], r[3])] > cost + d {
                    dist.insert((r[2], r[3]), cost + d);
                    pq.push(Reverse((cost + d, r[2], r[3])));
                }
            }
        }
        dist[&(target[0], target[1])]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    minimumCost(start: number[], target: number[], specialRoads: number[][]): number {
        const pts = new Set<string>();
        pts.add(`${start[0]},${start[1]}`);
        pts.add(`${target[0]},${target[1]}`);
        for (const r of specialRoads) {
            pts.add(`${r[0]},${r[1]}`);
            pts.add(`${r[2]},${r[3]}`);
        }
        const dist: Record<string, number> = {};
        for (const p of pts) dist[p] = Infinity;
        dist[`${start[0]},${start[1]}`] = 0;
        const pq: [number, number, number][] = [[0, start[0], start[1]]];
        while (pq.length) {
            pq.sort((a, b) => a[0] - b[0]);
            const [cost, x, y] = pq.shift()!;
            if (cost > dist[`${x},${y}`]) continue;
            const direct = Math.abs(x - target[0]) + Math.abs(y - target[1]);
            if (dist[`${target[0]},${target[1]}`] > cost + direct) {
                dist[`${target[0]},${target[1]}`] = cost + direct;
                pq.push([cost + direct, target[0], target[1]]);
            }
            for (const r of specialRoads) {
                const d = Math.abs(x - r[0]) + Math.abs(y - r[1]) + r[4];
                if (dist[`${r[2]},${r[3]}`] > cost + d) {
                    dist[`${r[2]},${r[3]}`] = cost + d;
                    pq.push([cost + d, r[2], r[3]]);
                }
            }
        }
        return dist[`${target[0]},${target[1]}`];
    }
}

Complexity

  • ⏰ Time complexity: O(N^2 + M log M) where N is the number of unique points and M is the number of edges processed by Dijkstra. Each point can be connected to every other, and Dijkstra’s heap operations dominate.
  • 🧺 Space complexity: O(N + M) for storing distances and the heap.