[Java] - Dijkstra's + DFS + Memoization + Explanation of problem description
As a note I spent 40 minutes trying to understand what this problem was asking. In classic fashion it finally dawned on me with 5 minutes left in the contest. I
As a note I spent 40 minutes trying to understand what this problem was asking. In classic fashion it finally dawned on me with 5 minutes left in the contest. I will try to explain below what the problem failed to explain (in my opinion). \n\n* Everything is pretty straight forward in the first two paragraphs. We get some edges that represent an undirected path between two different vertices. These paths are weighted. The path we are interested in is the one from `start` (node 1), to `end` (node `n`). Nothing new or overly complicated with this.\n\nThen comes this paragraph which can be very confusing as to what the question is asking you to accomplish. `The distance of a path is the sum of the weights on the edges of the path. Let distanceToLastNode(x) denote the shortest distance of a path between node n and node x. A restricted path is a path that also satisfies that distanceToLastNode(zi) > distanceToLastNode(zi+1) where 0 <= i <= k-1.` \n\n* After understanding the problem this makes sense but I think there should be some clarification. *If you are vertex x, then `distanceToLastNode(x)` is the shorteset path from the end vertex `n` to the vertex you are currently visiting `x`*. \n\n* I also think adding another line to clarify that you can travel to neighboring nodes, BUT you can only do so if the distance calculated for the neighboring node is less than the cost it took to travel to the node you are moving from. In other words, you can travel to neighboring nodes ONLY if the cost calculated from `distanceToLastNode(currentNode)` is less than `distanceToLastNode(neighbor)`.\n\n**Okay getting into the problem, it is broken into 3 different steps.**\n1) Create the graph. You can use a multitude of different data structures but you want to add all the edges in an undirected manner and keep track of the weights (you will use them later).\n\n2) Using Dijkstra\'s algorithm create the shortest path distance between vertex `n` and all other nodes. Now we have all the shortest paths from each node to the end, we will call this `distanceToEnd(node)`\n\n3) Start a DFS traversal from the start node `1` and travel as many different paths that you can. **HOWEVER** the requirement is that you can only move from a node to its neighbor if `distanceToEnd(node) > distanceToEnd(nei)`.\n\t* It is possible that we can travel multiple paths that reach the same node in its path, so we save those calculations for faster lookups. \n\nI hope this helps and if you have any questions feel free to ask.\n**Please upvote if this helped you!**\n\n```\nclass Solution {\n    private Map<Integer, List<int[]>> map = new HashMap<>();\n    private final static int mod = 1_000_000_007;\n    \n    public int countRestrictedPaths(int n, int[][] edges) {\n        for(int[] e : edges) {\n            map.computeIfAbsent(e[0], x -> new ArrayList<>()).add(new int[] { e[1], e[2] }); //create graph with weights\n            map.computeIfAbsent(e[1], x -> new ArrayList<>()).add(new int[] { e[0], e[2] });\n        }\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]); //sort based on weight (Dijkstra\'s)\n        pq.offer(new int[]{ n, 0 });\n        int[] dist = new int[n+1];\n        Arrays.fill(dist, Integer.MAX_VALUE); \n        dist[n] = 0;\n        \n        while(!pq.isEmpty()) {\n            int[] curr = pq.poll();\n            int node = curr[0];\n\t\t\tint weight = curr[1];\n            \n            for(int[] neighbor : map.get(node)) {\n                int nei = neighbor[0];\n                int w = weight + neighbor[1];\n                \n                if(w < dist[nei]) { //only traverse if this will create a shorter path. At the end we have all the shortest paths for each node from the last node, n.\n                    dist[nei] = w;\n                    pq.offer(new int[]{ nei, w });\n                }\n            }\n        }\n        Integer[] dp = new Integer[n+1];\n        return dfs(1, n, dist, dp);\n    }\n    public int dfs(int node, int end, int[] dist, Integer[] dp) {\n        if(node == end) return 1;\n        if(dp[node] != null) return dp[node];\n        long res = 0;\n        for(int[] neighbor : map.get(node)) {\n            int nei = neighbor[0];\n            if(dist[node] > dist[nei]) { //use our calculations from Dijkstra\'s to determine if we can travel to a neighbor.\n                res = (res + (dfs(nei, end, dist, dp)) % mod);\n            }\n        }\n        res = (res % mod);\n        return dp[node] = (int) res; //memoize for looking up values that have already been computed.\n    }\n}\n```
[]