🔥 21ms | beats 100% | Dijkstra with optimization
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Standard Dijkstra, [40ms](https://leetcode.com/problems/minimum-cost-to-reach-destination-in-time/submissions/894999497/)\n```java\nclass Solution {\n    record Node(int i, int t) {}\n    record Cell(int i, int t, int c) {}\n    public int minCost(int maxTime, int[][] edges, int[] fees) {\n        int n = fees.length;\n\n        // create the adjacency list graph\n        List<Node>[] g = new List[n];\n        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();\n        for (var e : edges) {\n            g[e[0]].add(new Node(e[1], e[2]));\n            g[e[1]].add(new Node(e[0], e[2]));\n        }\n\n        // Dijkstra\n        Queue<Cell> q = new PriorityQueue<>((a, b) -> a.c == b.c ? a.t - b.t : a.c - b.c);\n        int[] T = new int[n]; // 1. visited: de-dup 2. de-dup on worst time\n\n        q.offer(new Cell(0, 0, fees[0]));\n        Arrays.fill(T, maxTime + 1);\n        T[0] = 0;\n\n        while (!q.isEmpty()) {\n            var cur = q.poll();\n            if (cur.i == n-1) return cur.c;\n            \n            for (var nei : g[cur.i]) {\n                int t2 = cur.t + nei.t;\n                if (t2 >= T[nei.i]) continue; // if time is worst, no reason to continue\n                T[nei.i] = t2;\n                q.offer(new Cell(nei.i, t2, cur.c + fees[nei.i]));\n            }\n        }\n\n        return -1;\n    }\n}\n```\n\n# Optimize on time, early pruning [21ms](https://leetcode.com/problems/minimum-cost-to-reach-destination-in-time/submissions/895019270/)\n```java\nclass Solution {\n    record Node(int i, int t) {}\n    record Cell(int i, int t, int c) {}\n    public int minCost(int maxTime, int[][] edges, int[] fees) {\n        int n = fees.length;\n\n        // create the graph\n        List<Node>[] g = new List[n];\n        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();\n        for (var e : edges) {\n            g[e[0]].add(new Node(e[1], e[2]));\n            g[e[1]].add(new Node(e[0], e[2]));\n        }\n\n        // min time from end to each node\n        int[] time = new int[n];\n        Arrays.fill(time, Integer.MAX_VALUE);\n        time[n-1] = 0;\n        Queue<Integer> q = new PriorityQueue<>((a, b) -> time[a] - time[b]);\n        q.offer(n-1);\n        while (!q.isEmpty()) {\n            int cur = q.poll();\n            for (var nei : g[cur]) {\n                int t2 = time[cur] + nei.t;\n                if (t2 >= time[nei.i]) continue;\n                time[nei.i] = t2;\n                q.offer(nei.i);\n            }\n        }\n\n        // Dijkstra\n        Queue<Cell> q2 = new PriorityQueue<>((a, b) -> a.c - b.c);\n        int[] T = new int[n]; // 1. visited: de-dup 2. de-dup on worst time\n\n        q2.offer(new Cell(0, 0, fees[0]));\n        Arrays.fill(T, maxTime + 1);\n        T[0] = 0;\n\n        while (!q2.isEmpty()) {\n            var cur = q2.poll();\n            if (cur.i == n-1) return cur.c;\n            \n            for (var nei : g[cur.i]) {\n                int t2 = cur.t + nei.t;\n                if (time[nei.i] + t2 > maxTime) continue; // at this point we know we can skip\n                if (t2 >= T[nei.i]) continue; // if time is worst, no reason to continue\n                T[nei.i] = t2;\n                q2.offer(new Cell(nei.i, t2, cur.c + fees[nei.i]));\n            }\n        }\n\n        return -1;\n    }\n}\n```\n
['Java']