Description
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) to (1,2) with a cost of |1 - 1| + |2 - 1| = 1.
- (1,2) to (3,3). Use
specialRoads[0] with the cost 2.
- (3,3) to (3,4) with a cost of |3 - 3| + |4 - 3| = 1.
- (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) to (1,2) with a cost of |1 - 1| + |2 - 1| = 1.
- (1,2) to (7,4). Use
specialRoads[1] with the cost 4.
- (7,4) to (10,4) with a cost of |10 - 7| + |4 - 4| = 3.
Constraints:
start.length == target.length == 21 <= startX <= targetX <= 1051 <= startY <= targetY <= 1051 <= specialRoads.length <= 200specialRoads[i].length == 5startX <= x1i, x2i <= targetXstartY <= y1i, y2i <= targetY1 <= costi <= 105
Solutions
Solution 1: Dijkstra
We can find that for each coordinate (x, y) we visit, suppose the minimum cost from the start point to (x, y) is d. If we choose to move directly to (targetX, targetY), then the total cost is d + |x - targetX| + |y - targetY|. If we choose to go through a special path (x1, y1) → (x2, y2), then we need to spend |x - x1| + |y - y1| + cost to move from (x, y) to (x2, y2).
Therefore, we can use Dijkstra algorithm to find the minimum cost from the start point to all points, and then choose the smallest one from them.
We define a priority queue q, each element in the queue is a triple (d, x, y), which means that the minimum cost from the start point to (x, y) is d. Initially, we add (0, startX, startY) to the queue.
In each step, we take out the first element (d, x, y) in the queue, at this time we can update the answer, that is ans = min(ans, d + dist(x, y, targetX, targetY)). Then we enumerate all special paths (x1, y1) → (x2, y2) and add (d + dist(x, y, x1, y1) + cost, x2, y2) to the queue.
Finally, when the queue is empty, we can get the answer.
The time complexity is O(n2 × log n), and the space complexity is O(n2). Where n is the number of special paths.
PythonJavaC++GoTypeScript
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(code-box)
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);
}
}(code-box)
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;
}
};(code-box)
func minimumCost(start []int, target []int, specialRoads [][]int) int {
ans := 1 << 30
const n int = 1e6
pq := hp{{0, start[0], start[1]}}
vis := map[int]bool{}
for len(pq) > 0 {
p := pq[0]
heap.Pop(&pq)
d, x, y := p.d, p.x, p.y
if vis[x*n+y] {
continue
}
vis[x*n+y] = true
ans = min(ans, d+dist(x, y, target[0], target[1]))
for _, r := range specialRoads {
x1, y1, x2, y2, cost := r[0], r[1], r[2], r[3], r[4]
heap.Push(&pq, tuple{d + dist(x, y, x1, y1) + cost, x2, y2})
}
}
return ans
}
func dist(x1, y1, x2, y2 int) int {
return abs(x1-x2) + abs(y1-y2)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
type tuple struct {
d, x, y int
}
type hp []tuple
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].d < h[j].d }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }(code-box)
function minimumCost(start: number[], target: number[], specialRoads: number[][]): number {
const dist = (x1: number, y1: number, x2: number, y2: number): number => {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};
const q = new Heap<[number, number, number]>((a, b) => a[0] - b[0]);
q.push([0, start[0], start[1]]);
const n = 1000000;
const vis: Set<number> = new Set();
let ans = 1 << 30;
while (q.size()) {
const [d, x, y] = q.pop();
const k = x * n + y;
if (vis.has(k)) {
continue;
}
vis.add(k);
ans = Math.min(ans, d + dist(x, y, target[0], target[1]));
for (const [x1, y1, x2, y2, cost] of specialRoads) {
q.push([d + dist(x, y, x1, y1) + cost, x2, y2]);
}
}
return ans;
}
type Compare<T> = (lhs: T, rhs: T) => number;
class Heap<T = number> {
data: Array<T | null>;
lt: (i: number, j: number) => boolean;
constructor();
constructor(data: T[]);
constructor(compare: Compare<T>);
constructor(data: T[], compare: Compare<T>);
constructor(data: T[] | Compare<T>, compare?: (lhs: T, rhs: T) => number);
constructor(
data: T[] | Compare<T> = [],
compare: Compare<T> = (lhs: T, rhs: T) => (lhs < rhs ? -1 : lhs > rhs ? 1 : 0),
) {
if (typeof data === 'function') {
compare = data;
data = [];
}
this.data = [null, ...data];
this.lt = (i, j) => compare(this.data[i]!, this.data[j]!) < 0;
for (let i = this.size(); i > 0; i--) this.heapify(i);
}
size(): number {
return this.data.length - 1;
}
push(v: T): void {
this.data.push(v);
let i = this.size();
while (i >> 1 !== 0 && this.lt(i, i >> 1)) this.swap(i, (i >>= 1));
}
pop(): T {
this.swap(1, this.size());
const top = this.data.pop();
this.heapify(1);
return top!;
}
top(): T {
return this.data[1]!;
}
heapify(i: number): void {
while (true) {
let min = i;
const [l, r, n] = [i * 2, i * 2 + 1, this.data.length];
if (l < n && this.lt(l, min)) min = l;
if (r < n && this.lt(r, min)) min = r;
if (min !== i) {
this.swap(i, min);
i = min;
} else break;
}
}
clear(): void {
this.data = [null];
}
private swap(i: number, j: number): void {
const d = this.data;
[d[i], d[j]] = [d[j], d[i]];
}
}(code-box)
