LeetCode 2662: Minimum Cost of a Path With Special Roads Solution

Master LeetCode problem 2662 (Minimum Cost of a Path With Special Roads), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2662. Minimum Cost of a Path With Special Roads

Medium

Array Graph Heap (Priority Queue)Shortest Path

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming with a bit mask to keep track of which special roads have been used. We can create a function to calculate the minimum cost to reach a certain position while using some special roads.

Initialize a 2D array dp to store the minimum cost to reach each position from the starting position.
Create a recursive function dfs that takes the current position, the target position, and the bitmask indicating which special roads have been used.
In the dfs function, check if the current position is the target position. If so, return 0 as the cost is 0.
If the cost to reach the current position has already been calculated, return it from the dp array.
Iterate through all special roads and check if they can be used from the current position. If a special road can be used, recursively call the dfs function to calculate the cost.
Update the dp array with the minimum cost to reach the current position.
Return the minimum cost to reach the target position from the starting position.

Solution Code

class Solution {
    public int minimalCost(int[] start, int[] target, int[][] specialRoads) {
        int n = specialRoads.length;
        int[][] dp = new int[1 << n][n + 2];

        return dfs(start, target, specialRoads, 0, dp);
    }

    private int dfs(int[] cur, int[] target, int[][] specialRoads, int mask, int[][] dp) {
        int curIdx = mask >> specialRoads.length;
        if (cur[0] == target[0] && cur[1] == target[1]) {
            return 0;
        }
        if (dp[mask][curIdx] != 0) {
            return dp[mask][curIdx];
        }

        int res = Math.abs(target[0] - cur[0]) + Math.abs(target[1] - cur[1]);
        for (int i = 0; i < specialRoads.length; i++) {
            if ((mask & (1 << i)) == 0) {
                int[] road = specialRoads[i];
                if (cur[0] == road[0] && cur[1] == road[1]) {
                    res = Math.min(res, road[4] + dfs(new int[]{road[2], road[3]}, target, specialRoads, mask | (1 << i), dp));
                }
            }
        }

        dp[mask][curIdx] = res;
        return res;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2662 (Minimum Cost of a Path With Special Roads)?

This page provides optimized solutions for LeetCode problem 2662 (Minimum Cost of a Path With Special Roads) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2662 (Minimum Cost of a Path With Special Roads)?

The time complexity for LeetCode 2662 (Minimum Cost of a Path With Special Roads) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2662 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2662 in Java, C++, or Python.

Back to LeetCode Solutions