JAVA | 34 ms | Clean Memoization & Dijkstra's Algo
\nDijkstra\'s Algo : 34 ms\n\nclass Solution {\n    public int minCost(int maxTime, int[][] edges, int[] costVtx) {\n        int N = costVtx.length;\n        Ar
```\nDijkstra\'s Algo : 34 ms\n\nclass Solution {\n    public int minCost(int maxTime, int[][] edges, int[] costVtx) {\n        int N = costVtx.length;\n        ArrayList<int[]>[] graph = new ArrayList[N];\n        for(int i = 0; i < N ; i++) graph[i] = new ArrayList<>();\n        \n        for(int[] e : edges){\n            int u = e[0], v = e[1], w = e[2];\n            graph[u].add(new int[]{v, w});\n            graph[v].add(new int[]{u, w});\n        }\n        int[] timeHold = new int[N];\n        Arrays.fill(timeHold, (int) 1e9);\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> {\n            return a[1] - b[1];\n        });\n        // vtx | cost | time \n        pq.add(new int[]{0, costVtx[0], 0});\n        timeHold[0] = 0;\n        while(!pq.isEmpty()){\n            int[] p = pq.remove();\n            int vtx = p[0], cost = p[1], time = p[2]; \n            if(vtx == costVtx.length - 1) return cost;\n            for(int[] e : graph[vtx]){\n                int v = e[0], n_time = e[1];\n                if(time + n_time > maxTime) continue;\n                if(time + n_time < timeHold[v]){\n                    timeHold[v] = n_time + time;\n                    pq.add(new int[]{v, cost + costVtx[v], timeHold[v]});\n                }\n            }\n        }\n        return -1;\n    }\n}\n\nMemoization : 234 ms\n\nclass Solution {\n    ArrayList<int[]>[] graph;\n    int[][] dp;\n    public int minCost(int maxTime, int[][] edges, int[] passingFees) {\n        int n = 1000;\n        dp = new int[1001][maxTime + 1];\n        for(int[] d : dp) Arrays.fill(d, -1);\n        graph = new ArrayList[n];\n        for(int i = 0; i < n ; i++){\n            graph[i] = new ArrayList<>();\n        }\n        for(int[] e : edges){\n            int u = e[0], v = e[1], w = e[2];\n            graph[u].add(new int[]{v,w});\n            graph[v].add(new int[]{u,w});\n        }\n        int ans = costMaker(maxTime, passingFees, 0);\n        return ans >= (int) 1e8 ? -1 : ans;\n    }\n    \n    public int costMaker(int time, int[] fees, int src){\n        if(time < 0) return (int) 1e8;\n        if(src == fees.length - 1) return dp[src][time] =  fees[src];\n        if(dp[src][time] != -1) return dp[src][time];\n        int cost = (int) 1e8;\n        for(int[] e : graph[src]){\n            int v = e[0], w = e[1];\n            cost = Math.min(cost, costMaker(time - w, fees, v));\n        }\n        return dp[src][time] = cost + fees[src];\n    }\n}\n\n\n```\n
['Dynamic Programming', 'Depth-First Search', 'Memoization', 'Java']