Modified Dijkstra's with intuition
Instead of visited array that we normally put we have to make visited for time as there may exists a solution with more cost but with desired time and we have v
Instead of visited array that we normally put we have to make visited for time as there may exists a solution with more cost but with desired time and we have visited array for a node which might be come in the path of optimal solution we will miss the best solution\n\n```\nclass Solution {\n\n\tpublic int minCost(int maxTime, int[][] edges, int[] passingFees) {\n\t\tint dest = passingFees.length - 1;\n\t\tArrayList<Edge>[] graph = new ArrayList[passingFees.length];\n\t\tfor (int i = 0; i < graph.length; i++) {\n\t\t\tgraph[i] = new ArrayList();\n\t\t}\n\t\tfor (int i = 0; i < edges.length; i++) {\n\t\t\tint src = edges[i][0];\n\t\t\tint nbr = edges[i][1];\n\t\t\tint time = edges[i][2];\n\t\t\tgraph[src].add(new Edge(nbr, time, passingFees[src]));\n\t\t\tgraph[nbr].add(new Edge(src, time, passingFees[nbr]));\n\n\t\t}\n\t\tint[] visited = new int[passingFees.length];\n\t\tArrays.fill(visited, -1);\n\t\tPriorityQueue<Edge> q = new PriorityQueue<>();\n\t\tq.add(new Edge(0, 0, passingFees[0]));\n\t\twhile (!q.isEmpty()) {\n\t\t\tEdge r = q.poll();\n\t\t\tif (r.nbr == dest)\n\t\t\t\treturn r.fees;\n\t\t\tfor (Edge nbr : graph[r.nbr]) {\n\t\t\t\tif (visited[nbr.nbr] != -1 && r.time + nbr.time >= visited[nbr.nbr])\n\t\t\t\t\tcontinue;\n\t\t\t\tvisited[nbr.nbr] = r.time + nbr.time;\n\t\t\t\tif (r.time + nbr.time <= maxTime) {\n\t\t\t\t\tq.add(new Edge(nbr.nbr, r.time + nbr.time, r.fees + passingFees[nbr.nbr]));\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\treturn -1;\n\t}\n\n\tpublic static class Edge implements Comparable<Edge> {\n\n\t\tint nbr;\n\t\tint time;\n\t\tint fees;\n\n\t\tpublic Edge(int nbr, int time, int fees) {\n\n\t\t\tthis.nbr = nbr;\n\t\t\tthis.time = time;\n\t\t\tthis.fees = fees;\n\t\t}\n\n\t\tpublic int compareTo(Edge o) {\n\t\t\treturn this.fees - o.fees;\n\t\t}\n\t}\n}
['Breadth-First Search', 'Heap (Priority Queue)', 'Java']