DevExCode

2662. Minimum Cost of a Path With Special Roads

ArrayGraphHeap (Priority Queue)Shortest Path

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.

  1. Initialize a 2D array dp to store the minimum cost to reach each position from the starting position.
  2. Create a recursive function dfs that takes the current position, the target position, and the bitmask indicating which special roads have been used.
  3. In the dfs function, check if the current position is the target position. If so, return 0 as the cost is 0.
  4. If the cost to reach the current position has already been calculated, return it from the dp array.
  5. 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.
  6. Update the dp array with the minimum cost to reach the current position.
  7. Return the minimum cost to reach the target position from the starting position.

:

View Leetcode Problem
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;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question