Minimum Cost to Complete Journey with Time Constraint Using Dijkstra's Algorithm
Intuition

The problem is essentially about finding the shortest path in a weighted graph, where the nodes represent cities, and the edges represent roads conne
### **Intuition**
- The problem is essentially about finding the **shortest path** in a **weighted graph**, where the nodes represent cities, and the edges represent roads connecting these cities with certain travel times. The challenge here is that, in addition to the usual **distance or path cost**, we also have an additional **cost constraint**, i.e., the passing fee for each city you visit. You want to minimize this total cost while respecting the constraint on the total travel time.
  
- To solve this, we need to explore different paths from the starting city to the destination city, but we must ensure that:
  1. The **time** taken to travel doesn't exceed the `maxTime`.
  2. The **cost** of passing through the cities is minimized.

- This problem can be approached by using **Dijkstra's algorithm** with a slight modification:
  - Instead of just tracking the shortest distance to a node, we also track the **total cost** incurred from passing through the cities.
  - We maintain a priority queue to always process the path that has the minimum **cost** (and within the allowed **time**).

---

### **Approach**
1. **Graph Representation**:  
   We start by building an adjacency list (graph) where each node (city) is connected to its neighbors via roads (edges). Each edge has a travel time.

2. **Priority Queue**:  
   We use a **min-heap (priority queue)** to always expand the node with the minimum total cost and time to reach it. This allows us to efficiently explore paths with lower costs first.

3. **Tracking Costs and Times**:
   - `costs[i]`: Tracks the minimum cost to reach city `i`. We initialize it to infinity for all cities except the starting city (city 0), which has a cost equal to its passing fee.
   - `times[i]`: Tracks the minimum time required to reach city `i`. We initialize it to `maxTime + 1` for all cities, except for city 0, which has a time of 0.
  
4. **Exploring Neighbors**:
   For each city, we explore all of its neighbors. For each neighboring city, we compute the new time and cost if we were to travel from the current city. If the new time exceeds `maxTime`, we skip that path. Otherwise, if the new cost is lower than the previously recorded cost for that city, we update the cost and time and add the neighbor to the priority queue for further exploration.

5. **Termination**:
   If we reach the destination city (`n - 1`), we return the total cost incurred to reach it. If no valid path exists within the time constraint, return `-1`.

---

### **Complexity**

- **Time complexity**:  
  The algorithm primarily operates by extracting elements from the priority queue and relaxing edges. The priority queue supports insertions and extractions in **O(log n)** time.  
  Since we process each edge and each node at most once, the total time complexity is **O(E log V)**, where:
  - **E** is the number of edges (roads),
  - **V** is the number of vertices (cities).

- **Space complexity**:  
  We store the graph in an adjacency list, which requires **O(E)** space. Additionally, we store the `costs`, `times`, and the priority queue, which requires **O(V)** space. Thus, the total space complexity is **O(V + E)**.

# Code
```python3 []
import heapq
from collections import defaultdict
from typing import List

class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        # Number of cities
        n = len(passingFees)
        
        # Create a graph to store cities and the time required to travel between them
        graph = defaultdict(list)
        
        # Fill the graph with the roads (edges)
        for u, v, time in edges:
            graph[u].append((v, time))
            graph[v].append((u, time))
        
        # Initialize cost array: costs[i] will hold the minimum cost to reach city i
        costs = [float("inf")] * n
        # Initialize time array: times[i] will hold the minimum time to reach city i
        times = [maxTime + 1] * n
        # Starting at city 0 with its passing fee
        times[0] = 0
        costs[0] = passingFees[0]
        
        # Min-heap (priority queue) to always expand the node with the least cost and time
        queue = [(passingFees[0], 0, 0)]  # (current total cost, current time, current city)
        
        while queue:
            # Pop the city with the smallest cost and time from the priority queue
            curr_cost, curr_time, curr_city = heapq.heappop(queue)

            # If we have reached the destination city (city n - 1), return the cost
            if curr_city == n - 1:
                return curr_cost
            
            # Explore all the neighboring cities (neighbors and the time to reach them)
            for next_city, travel_time in graph[curr_city]:
                # If traveling to the next city exceeds the maxTime, skip this path
                if curr_time + travel_time > maxTime:
                    continue
                
                # Calculate the new time and cost after moving to the next city
                new_time = curr_time + travel_time
                new_cost = curr_cost + passingFees[next_city]
                
                # If we find a cheaper way to reach next_city, update the cost and time
                if new_cost < costs[next_city] or new_time < times[next_city]:
                    costs[next_city] = new_cost
                    times[next_city] = new_time
                    # Push the updated city state into the priority queue
                    heapq.heappush(queue, (new_cost, new_time, next_city))
        
        # If we cannot reach the destination city within the allowed time, return -1
        return -1

```
['Graph', 'Python3']