Simple Dijkstra's algorithm | C++ | Java | Python
Intuition\nSince source-single destination. Bellman-ford and Dijkstra come to mind? \n\n# Approach\nDijksta\'s algorithm. You can hear more in the linked video:
# Intuition\nSince source-single destination. Bellman-ford and Dijkstra come to mind? \n\n# Approach\nDijksta\'s algorithm. You can hear more in the linked video: \n\n# Complexity\n- Time complexity: O(N)\n\n- Space complexity: O(N log N)\n\n# Code\n```java []\nclass Solution {\n    public int minCost(int maxTime, int[][] edges, int[] passingFees) {\n        int n = passingFees.length;\n        List<Edge>[] adj = new ArrayList[n];\n        for (int k = 0; k < n; k++) {\n            adj[k] = new ArrayList();\n        }\n        for (int k = 0; k < edges.length; k++) {\n            int[] edge = edges[k];\n            int u = edge[0];\n            int v = edge[1];\n            int t = edge[2];\n            adj[u].add(new Edge(v, t, passingFees[v]));\n            adj[v].add(new Edge(u, t, passingFees[u]));\n        }\n\n        int[] minTime = new int[n];\n        Arrays.fill(minTime, Integer.MAX_VALUE);\n\n        PriorityQueue<Edge> pq = new PriorityQueue<>((a, b)-> (a.cost == b.cost)? a.time - b.time : a.cost - b.cost);// Consider only cost for ordering\n        pq.add(new Edge(0, 0, passingFees[0]));\n\n        while (!pq.isEmpty()) {\n            Edge current = pq.poll();\n            int currentNode = current.node;\n            int currentTime = current.time;\n            int currentCost = current.cost;\n\n            if (currentTime > maxTime || currentTime >= minTime[currentNode]){\n                continue;\n            }\n            \n            if (currentNode == n - 1) {\n                return currentCost; // We have reached the destination\n            }\n\n            minTime[currentNode] = currentTime; // Update the minTime for this node\n\n            for (Edge neighborEdge : adj[currentNode]) {\n                int neighbor = neighborEdge.node;\n                int newTime = neighborEdge.time + currentTime;\n                int newCost = neighborEdge.cost + currentCost;\n\n                if (newTime <= maxTime) {\n                    pq.add(new Edge(neighbor, newTime, newCost));\n                }\n            }\n        }\n\n        return -1; // If we can\'t reach the destination within maxTime\n    }\n\n    public class Edge {\n        int node;\n        int time;\n        int cost;\n\n        public Edge(int node, int time, int cost) {\n            this.node = node;\n            this.time = time;\n            this.cost = cost;\n        }\n    }\n}\n```\n```python []\nfrom heapq import heappush, heappop\n\nclass Solution:\n    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:\n        n = len(passingFees)\n        adj = [[] for _ in range(n)]\n        for edge in edges:\n            u, v, t = edge\n            adj[u].append((v, t, passingFees[v]))\n            adj[v].append((u, t, passingFees[u]))\n\n        minTime = [float(\'inf\') for _ in range(n)]\n        pq = []\n        heappush(pq, (passingFees[0], 0, 0))  # cost, time, node\n\n        while pq:\n            cost, time, node = heappop(pq)\n\n            if time > maxTime or time >= minTime[node]:\n                continue\n\n            if node == n - 1:\n                return cost\n\n            minTime[node] = time\n\n            for v, t, c in adj[node]:\n                if time + t <= maxTime:\n                    heappush(pq, (cost + c, time + t, v))\n\n        return -1\n```\n```c++ []\n#include <vector>\n#include <queue>\n\nusing namespace std;\n\nclass Solution {\npublic:\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {\n        int n = passingFees.size();\n        vector<vector<pair<int, pair<int, int>>>> adj(n); // {node, {time, cost}}\n        \n        for(auto& edge : edges) {\n            int u = edge[0], v = edge[1], t = edge[2];\n            adj[u].push_back({v, {t, passingFees[v]}});\n            adj[v].push_back({u, {t, passingFees[u]}});\n        }\n\n        vector<int> minTime(n, INT_MAX);\n        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq; // {cost, {time, node}}\n        pq.push({passingFees[0], {0, 0}});\n        \n        while(!pq.empty()) {\n            int cost = pq.top().first, time = pq.top().second.first, node = pq.top().second.second;\n            pq.pop();\n\n            if(time > maxTime || time >= minTime[node]) continue;\n\n            if(node == n - 1) return cost;\n\n            minTime[node] = time;\n\n            for(auto& next : adj[node]) {\n                int v = next.first, t = next.second.first, c = next.second.second;\n                if(time + t <= maxTime) {\n                    pq.push({cost + c, {time + t, v}});\n                }\n            }\n        }\n\n        return -1;\n    }\n};\n\n```
['Breadth-First Search', 'Heap (Priority Queue)', 'Python', 'C++', 'Java']