Java Solution | Dijkstra | Best First Search
The base idea is to extend Dijkstra algorithm, or better to be called "Best first search" for easy understanding. Despite being wikipedia, I really recommend a 
The base idea is to extend Dijkstra algorithm, or better to be called "Best first search" for easy understanding. Despite being wikipedia, I really recommend a deep read of it https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm. We maintain a Priority Queue, and the Queue tracks best candidates that could lead to desired outcome: minimum cost to the destination.\n\nBut, how do you model the constraint of time? You can just play blind for now, ignore it being a constraint, check every item in the queue as you would in regular single source best path problem, AND, whenever you find a solution, that is we reached the destination using best candidates from Priority Queue, you check the arrival time! If it exceeds the limit, we just dig into our queue again, until we found one, return the cost, or we give up, return -1.\n\nNow, several traps / important insights of this problem:\n\n- You must also insert a <location, time, cost> tuple into the queue even when the cost is sub-optimal. Why? Bcoz the optimal guy *could* result in time out! Therefore, you must also *compromise* by adding sub optimal tuples. But again, if we behave desperate by adding anything, you will get TLE... So, we only add tuples when there are *potential for improvements*, that is\n\t- reduce in cost OR\n\t- reduce in time cost.\n- Another early stopping opportunity: before you insert tuples into the queue, if its present time cost already > maxTime, we avoid insertion.\n\nNow we have walked through the general ideas + the problem specific tricks, here is the java code. Note that the comparator is kind of niche, you can just compare only on cost, and still acquire the similar performance, hinting the case of same cost different time has low impact on the overall computation.\n\n```\nclass Record {\n    int loc;\n    int cost;\n    int time;\n    \n    public Record(int loc, int cost, int time) {\n        this.loc = loc;\n        this.cost = cost;\n        this.time = time;\n    }\n    \n    public int compareTo(Record other) {\n        // First compare cost, if same, track time.\n        if (this.cost > other.cost) {\n            return 1;\n        } else if (this.cost < other.cost) {\n            return -1;\n        } else if (this.time > other.time) {\n            return 1;\n        } else if (this.time < other.time) {\n            return -1;\n        } else {\n            return 0;\n        }\n    }\n}\n\nclass RecordCompare implements Comparator<Record> {\n    @Override\n    public int compare (Record a, Record b) {\n        return a.compareTo(b);\n    }\n}\n\nclass Solution {\n    public int minCost(int maxTime, int[][] edges, int[] passingFees) {\n        // Build adj matrix of time cost.\n        int[][] time_adj = new int[passingFees.length][passingFees.length];\n        for (int i = 0; i < time_adj.length; i++) {\n            for (int j = 0; j < time_adj[0].length; j++) {\n                time_adj[i][j] = -1;\n            }\n        }\n        \n        for (int[] rd : edges) {\n            if (time_adj[rd[0]][rd[1]] == -1 ||\n                time_adj[rd[0]][rd[1]] > rd[2]) {\n                time_adj[rd[0]][rd[1]] = rd[2];\n                time_adj[rd[1]][rd[0]] = rd[2];\n            }\n        }\n        \n        // Best first search as if Dijkstra algorithm.\n        // PQ which tracks the cost. \n        // PriorityQueue<Record> bestQueue = new PriorityQueue<Record>(10, \n        //                                       ((o1, o2) -> o1.cost - o2.cost));\n        PriorityQueue<Record> bestQueue = new PriorityQueue<Record>(10, new RecordCompare());\n        \n        bestQueue.offer(new Record(0, passingFees[0], 0));\n        // Helper arrays for early stopping. We don\'t need to explore worse \n        // candidates vs. those in the bestQueue.\n        int[] bestTime = new int[passingFees.length];\n        int[] bestCost = new int[passingFees.length];\n        bestTime[0] = 0;\n        bestCost[0] = passingFees[0];\n        for (int i = 1; i < passingFees.length; i++) {\n            bestTime[i] = maxTime + 1;\n            bestCost[i] = Integer.MAX_VALUE;\n        }\n        \n        while (bestQueue.size() >0) {\n            Record curNode = bestQueue.poll();\n            \n            // Check result.\n            if (curNode.loc == passingFees.length - 1 &&\n                curNode.time <= maxTime) {\n                return curNode.cost;\n            }\n            \n            for (int i = 0; i < passingFees.length; i++) {\n                if (i == curNode.loc) {\n                    continue;\n                }\n                \n                if (time_adj[curNode.loc][i] != -1 &&\n                    (bestTime[i] > (curNode.time + time_adj[curNode.loc][i]) ||\n                     bestCost[i] > (curNode.cost + passingFees[i]))\n                   ) {\n                    \n                    // No hope, early stop.\n                    if (curNode.time + time_adj[curNode.loc][i] > maxTime) {\n                        continue;\n                    }\n                    \n                    bestTime[i] = (curNode.time + time_adj[curNode.loc][i]);\n                    bestCost[i] = (curNode.cost + passingFees[i]);\n                    \n                    bestQueue.offer(new Record(i, bestCost[i], bestTime[i]));\n                }\n            }\n            \n        }\n        \n        return -1;\n    }\n}\n```
[]