1class Solution {
2    public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
3        // Initialize the minimum cost to a large value
4        int minCost = 1 << 30;
5      
6        // Large constant used for encoding coordinates into a single long value
7        int COORDINATE_MULTIPLIER = 1000000;
8      
9        // Priority queue to store states: [cost, x, y], ordered by cost
10        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
11      
12        // Set to track visited positions (encoded as long values)
13        Set<Long> visited = new HashSet<>();
14      
15        // Start from the initial position with cost 0
16        priorityQueue.offer(new int[] {0, start[0], start[1]});
17      
18        // Dijkstra's algorithm to find the minimum cost path
19        while (!priorityQueue.isEmpty()) {
20            int[] current = priorityQueue.poll();
21            int currentCost = current[0];
22            int currentX = current[1];
23            int currentY = current[2];
24          
25            // Encode current position as a single long value for visited check
26            long encodedPosition = 1L * currentX * COORDINATE_MULTIPLIER + currentY;
27          
28            // Skip if this position has already been visited
29            if (visited.contains(encodedPosition)) {
30                continue;
31            }
32          
33            // Mark current position as visited
34            visited.add(encodedPosition);
35          
36            // Update minimum cost if we can reach target from current position
37            int costToTarget = currentCost + dist(currentX, currentY, target[0], target[1]);
38            minCost = Math.min(minCost, costToTarget);
39          
40            // Explore all special roads from current position
41            for (int[] road : specialRoads) {
42                int roadStartX = road[0];
43                int roadStartY = road[1];
44                int roadEndX = road[2];
45                int roadEndY = road[3];
46                int roadCost = road[4];
47              
48                // Calculate total cost to reach the end of this special road
49                int costToRoadStart = dist(currentX, currentY, roadStartX, roadStartY);
50                int totalCost = currentCost + costToRoadStart + roadCost;
51              
52                // Add new state to priority queue
53                priorityQueue.offer(new int[] {totalCost, roadEndX, roadEndY});
54            }
55        }
56      
57        return minCost;
58    }
59  
60    /**
61     * Calculate Manhattan distance between two points
62     * @param x1 x-coordinate of first point
63     * @param y1 y-coordinate of first point
64     * @param x2 x-coordinate of second point
65     * @param y2 y-coordinate of second point
66     * @return Manhattan distance between the two points
67     */
68    private int dist(int x1, int y1, int x2, int y2) {
69        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
70    }
71}
72

1class Solution {
2public:
3    int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
4        // Lambda function to calculate Manhattan distance between two points
5        auto calculateManhattanDistance = [](int x1, int y1, int x2, int y2) {
6            return abs(x1 - x2) + abs(y1 - y2);
7        };
8      
9        // Initialize the minimum cost to a large value
10        int minCost = 1 << 30;  // Equivalent to 2^30
11      
12        // Constant for encoding coordinates into a single value
13        const int ENCODING_FACTOR = 1e6;
14      
15        // Priority queue for Dijkstra's algorithm
16        // Stores tuples of (distance, x-coordinate, y-coordinate)
17        // Using greater<> for min-heap behavior
18        priority_queue<tuple<int, int, int>, 
19                      vector<tuple<int, int, int>>, 
20                      greater<tuple<int, int, int>>> pq;
21      
22        // Start from the initial position with cost 0
23        pq.push({0, start[0], start[1]});
24      
25        // Set to track visited positions to avoid revisiting
26        unordered_set<long long> visitedPositions;
27      
28        // Dijkstra's algorithm main loop
29        while (!pq.empty()) {
30            // Extract the position with minimum distance
31            auto [currentDistance, currentX, currentY] = pq.top();
32            pq.pop();
33          
34            // Encode current position into a single value for visited check
35            long long encodedPosition = 1LL * currentX * ENCODING_FACTOR + currentY;
36          
37            // Skip if this position has already been visited
38            if (visitedPositions.count(encodedPosition)) {
39                continue;
40            }
41          
42            // Mark current position as visited
43            visitedPositions.insert(encodedPosition);
44          
45            // Update minimum cost by considering direct path from current position to target
46            minCost = min(minCost, 
47                         currentDistance + calculateManhattanDistance(currentX, currentY, 
48                                                                      target[0], target[1]));
49          
50            // Explore all special roads from current position
51            for (auto& road : specialRoads) {
52                int roadStartX = road[0];
53                int roadStartY = road[1];
54                int roadEndX = road[2];
55                int roadEndY = road[3];
56                int roadCost = road[4];
57              
58                // Calculate total cost: current distance + distance to road start + road cost
59                int totalCost = currentDistance + 
60                               calculateManhattanDistance(currentX, currentY, roadStartX, roadStartY) + 
61                               roadCost;
62              
63                // Add the road's end position to the priority queue
64                pq.push({totalCost, roadEndX, roadEndY});
65            }
66        }
67      
68        return minCost;
69    }
70};
71

1// Calculate Manhattan distance between two points
2function calculateManhattanDistance(x1: number, y1: number, x2: number, y2: number): number {
3    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
4}
5
6// Compare function for priority queue (min-heap based on cost)
7function compareByCost(a: [number, number, number], b: [number, number, number]): number {
8    return a[0] - b[0];
9}
10
11// Main function to find minimum cost path from start to target using special roads
12function minimumCost(start: number[], target: number[], specialRoads: number[][]): number {
13    // Priority queue to store [cost, x, y] tuples, ordered by cost
14    const priorityQueue = new Heap<[number, number, number]>(compareByCost);
15  
16    // Start from the initial position with cost 0
17    priorityQueue.push([0, start[0], start[1]]);
18  
19    // Constant for encoding coordinates into a single number
20    const COORDINATE_MULTIPLIER = 1000000;
21  
22    // Set to track visited positions to avoid revisiting
23    const visitedPositions: Set<number> = new Set();
24  
25    // Initialize answer with a large value
26    let minimumTotalCost = 1 << 30;
27  
28    // Dijkstra's algorithm to find shortest path
29    while (priorityQueue.size()) {
30        // Get the position with minimum cost so far
31        const [currentCost, currentX, currentY] = priorityQueue.pop();
32      
33        // Encode current position as a single number for efficient storage
34        const encodedPosition = currentX * COORDINATE_MULTIPLIER + currentY;
35      
36        // Skip if this position has already been visited
37        if (visitedPositions.has(encodedPosition)) {
38            continue;
39        }
40      
41        // Mark current position as visited
42        visitedPositions.add(encodedPosition);
43      
44        // Update minimum cost if direct path from current position to target is better
45        minimumTotalCost = Math.min(
46            minimumTotalCost, 
47            currentCost + calculateManhattanDistance(currentX, currentY, target[0], target[1])
48        );
49      
50        // Explore all special roads from current position
51        for (const [roadStartX, roadStartY, roadEndX, roadEndY, roadCost] of specialRoads) {
52            // Calculate total cost: current cost + distance to road start + road cost
53            const totalCostToRoadEnd = currentCost + 
54                calculateManhattanDistance(currentX, currentY, roadStartX, roadStartY) + 
55                roadCost;
56          
57            // Add road end position to priority queue for exploration
58            priorityQueue.push([totalCostToRoadEnd, roadEndX, roadEndY]);
59        }
60    }
61  
62    return minimumTotalCost;
63}
64
65// Type definition for comparison function
66type Compare<T> = (lhs: T, rhs: T) => number;
67
68// Min-heap implementation for priority queue
69class Heap<T = number> {
70    // Internal array storage with null at index 0 for easier indexing
71    data: Array<T | null>;
72    // Comparison function for heap ordering
73    lt: (i: number, j: number) => boolean;
74  
75    // Constructor overloads
76    constructor();
77    constructor(data: T[]);
78    constructor(compare: Compare<T>);
79    constructor(data: T[], compare: Compare<T>);
80    constructor(
81        data: T[] | Compare<T> = [],
82        compare: Compare<T> = (lhs: T, rhs: T) => (lhs < rhs ? -1 : lhs > rhs ? 1 : 0),
83    ) {
84        // Handle case where first parameter is comparison function
85        if (typeof data === 'function') {
86            compare = data;
87            data = [];
88        }
89      
90        // Initialize data array with null at index 0 for 1-based indexing
91        this.data = [null, ...data];
92      
93        // Define less-than comparison using provided compare function
94        this.lt = (i, j) => compare(this.data[i]!, this.data[j]!) < 0;
95      
96        // Heapify all elements to maintain heap property
97        for (let i = this.size(); i > 0; i--) {
98            this.heapify(i);
99        }
100    }
101
102    // Return number of elements in heap
103    size(): number {
104        return this.data.length - 1;
105    }
106
107    // Add new element and maintain heap property
108    push(v: T): void {
109        this.data.push(v);
110        let currentIndex = this.size();
111      
112        // Bubble up: swap with parent while current is smaller
113        while (currentIndex >> 1 !== 0 && this.lt(currentIndex, currentIndex >> 1)) {
114            this.swap(currentIndex, currentIndex >> 1);
115            currentIndex >>= 1;
116        }
117    }
118
119    // Remove and return minimum element
120    pop(): T {
121        // Move last element to root
122        this.swap(1, this.size());
123        const minElement = this.data.pop();
124      
125        // Restore heap property from root
126        this.heapify(1);
127        return minElement!;
128    }
129
130    // Return minimum element without removing
131    top(): T {
132        return this.data[1]!;
133    }
134  
135    // Restore heap property starting from index i
136    heapify(i: number): void {
137        while (true) {
138            let minIndex = i;
139            const leftChild = i * 2;
140            const rightChild = i * 2 + 1;
141            const heapSize = this.data.length;
142          
143            // Find minimum among current node and its children
144            if (leftChild < heapSize && this.lt(leftChild, minIndex)) {
145                minIndex = leftChild;
146            }
147            if (rightChild < heapSize && this.lt(rightChild, minIndex)) {
148                minIndex = rightChild;
149            }
150          
151            // If current is not minimum, swap and continue
152            if (minIndex !== i) {
153                this.swap(i, minIndex);
154                i = minIndex;
155            } else {
156                break;
157            }
158        }
159    }
160
161    // Remove all elements from heap
162    clear(): void {
163        this.data = [null];
164    }
165
166    // Swap elements at indices i and j
167    private swap(i: number, j: number): void {
168        const tempData = this.data;
169        [tempData[i], tempData[j]] = [tempData[j], tempData[i]];
170    }
171}
172