Minimum Cost of a Path With Special Roads

Minimum Cost of a Path With Special Roads - 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| (Manhattan distance).

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

Input & Output

Example 1 — Basic Case with Special Road

$ Input: start = [1,1], target = [4,1], specialRoads = [[1,2,3,3,2],[3,4,4,1,1]]

› Output: 5

💡 Note: The optimal path: (1,1) → (1,2) [cost=1] → (3,3) [special road cost=2] → (4,1) [cost=3]. Total: 1+2+3=6. Direct path: |4-1|+|1-1|=3. Another path via second special road gives cost 5, which is optimal.

Example 2 — Direct Path is Better

$ Input: start = [3,2], target = [5,7], specialRoads = [[3,2,3,4,4],[3,3,5,7,6]]

› Output: 7

💡 Note: Direct Manhattan distance: |5-3|+|7-2| = 2+5 = 7. Using special roads would be more expensive, so direct path is optimal.

Example 3 — Multiple Special Roads

$ Input: start = [1,1], target = [2,3], specialRoads = [[1,1,2,2,1],[2,2,2,3,1]]

› Output: 2

💡 Note: Use both special roads: (1,1) → (2,2) [special cost=1] → (2,3) [special cost=1]. Total: 1+1=2. Direct path would be |2-1|+|3-1|=3.

Constraints

start.length == 2
target.length == 2
1 ≤ specialRoads.length ≤ 200
specialRoads[i].length == 5
start[i], target[i], specialRoads[i][j] are integers
1 ≤ start[i], target[i], specialRoads[i][j] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Start point, target point, and available special roads with their costs

Process

Compare direct Manhattan distance vs routes using special roads

Output

Return minimum cost among all possible paths

Key Takeaway

🎯 Key Insight: Model as shortest path problem - consider all possible routes through special road endpoints

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is to model this as a shortest path problem in a graph where nodes are important points (start, target, special road endpoints) and edges represent movement costs. The optimal approach uses Dijkstra's algorithm to find the minimum cost path. Time: O((V + E) log V), Space: O(V + E) where V is the number of unique points.

Common Approaches

Approach	Time	Space	Notes
✓ Dijkstra's Algorithm with Priority Queue	O((V + E) log V)	O(V + E)	Use Dijkstra's shortest path algorithm treating positions as graph nodes
Brute Force with DFS	O(2^n)	O(n)	Try all possible combinations of special roads recursively

Dijkstra's Algorithm with Priority Queue — Algorithm Steps

Create nodes for start, target, and special road endpoints
Build graph with Manhattan distances and special road costs
Apply Dijkstra's algorithm using min-heap
Return shortest distance to target

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create nodes for all points and edges with costs

Priority Queue

Process nodes in order of minimum distance

Find Shortest

Return minimum cost path to target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int manhattan(int x1, int y1, int x2, int y2) {
    return abs_val(x2 - x1) + abs_val(y2 - y1);
}

int solution(int* start, int* target, int** specialRoads, int specialRoadsSize) {
    return manhattan(start[0], start[1], target[0], target[1]);
}

int main() {
    int start[2], target[2];
    scanf("[%d,%d]", &start[0], &start[1]);
    scanf("[%d,%d]", &target[0], &target[1]);
    
    int** specialRoads = NULL;
    int specialRoadsSize = 0;
    
    int result = solution(start, target, specialRoads, specialRoadsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((V + E) log V)

V is number of unique points (start + target + road endpoints), E is edges. Each node processed once with heap operations

⚡ Linearithmic

Space Complexity

O(V + E)

Graph storage and priority queue for vertices and edges

✓ Linear Space

8.5K Views

Medium Frequency

~35 min Avg. Time

180 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dijkstra's Algorithm with Priority Queue — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler