Minimum Cost of a Path With Special Roads solution and explanation

import heapq

def minimumCost(start, target, specialRoads):
    startX, startY = start
    targetX, targetY = target
    # min-heap (priority queue)
    heap = [(0, startX, startY)]
    visited = set()
    while heap:
        cost, x, y = heapq.heappop(heap)
        # Check if we reached the target
        if (x, y) == (targetX, targetY):
            return cost
        if (x, y) in visited:
            continue
        visited.add((x, y))
        # Consider using special roads
        for x1, y1, x2, y2, roadCost in specialRoads:
            if (x, y) == (x1, y1) and (x2, y2) not in visited:
                heapq.heappush(heap, (cost + roadCost, x2, y2))
        # Consider moving directly to the target
        directCost = abs(targetX - x) + abs(targetY - y)
        heapq.heappush(heap, (cost + directCost, targetX, targetY))

function minimumCost(start, target, specialRoads) {
    let [startX, startY] = start;
    let [targetX, targetY] = target;
    const pq = new MinPriorityQueue({ priority: (x) => x[0] });
    pq.enqueue([0, startX, startY]);
    const visited = new Set();

    while (!pq.isEmpty()) {
        const [cost, x, y] = pq.dequeue().element;
        if (x === targetX && y === targetY) return cost;
        if (visited.has(`${x},${y}`)) continue;
        visited.add(`${x},${y}`);

        for (const [x1, y1, x2, y2, roadCost] of specialRoads) {
            if (x === x1 && y === y1 && !visited.has(`${x2},${y2}`)) {
                pq.enqueue([cost + roadCost, x2, y2]);
            }
        }
        // Push the target as final destination which simulates direct moving
        pq.enqueue([cost + Math.abs(targetX - x) + Math.abs(targetY - y), targetX, targetY]);
    }
}

import java.util.*;

public class Solution {
    public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
        int startX = start[0], startY = start[1], targetX = target[0], targetY = target[1];
        List<int[]> edges = new ArrayList<>();
        // Add direct path edge
        edges.add(new int[]{startX, startY, targetX, targetY, Math.abs(targetX - startX) + Math.abs(targetY - startY)});
        for (int[] road : specialRoads) {
            edges.add(road);
        }
        int dist = Integer.MAX_VALUE;
        for (int i = 0; i < edges.size(); ++i) {
            boolean changed = false;
            for (int[] road : edges) {
                int x1 = road[0], y1 = road[1], x2 = road[2], y2 = road[3], cost = road[4];
                if (Math.abs(targetX - x2) + Math.abs(targetY - y2) < dist) {
                    dist = Math.min(dist, cost);
                    changed = true;
                }
            }
            if (!changed) break;
        }
        return dist;
    }
}

#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
    int startX = start[0], startY = start[1], targetX = target[0], targetY = target[1];
    vector<vector<int>> edges;
    // Add direct path from start to target
    edges.push_back({startX, startY, targetX, targetY, abs(targetX - startX) + abs(targetY - startY)});
    for (auto& road : specialRoads) {
        edges.push_back(road);
    }
    int dist = INT_MAX;
    for (int i = 0; i < edges.size(); ++i) {
        int changed = false;
        for (auto& edge : edges) {
            int x1 = edge[0], y1 = edge[1], x2 = edge[2], y2 = edge[3], cost = edge[4];
            if (abs(targetX - x2) + abs(targetY - y2) < dist) {
                dist = cost;
                changed = true;
            }
        }
        if (!changed) break;
    }
    return dist;
}

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]];
    }
}

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 }