def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        
        # Dijkstra's Algorithm (Single-Source Shortest Path):
        # We want the minimum time for a signal sent from node k
        # to reach all n nodes in a directed graph with non-negative weights.
        
        # Key Ideas:
        #   1. Model the network as a directed weighted graph.
        #   2. Use a min-heap to always expand the node with the smallest
        #      known signal arrival time.
        #   3. Maintain a dictionary of shortest known times to each node.
        #   4. If all nodes are reached, return the maximum of these times.
        #   5. If some node is unreachable, return -1.

        # Build adjacency list: graph[src] = [(dest, weight), ...]
        # tc: O(edge)
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        
        # Min-Heap:
        # Each entry is (time_to_reach_node, node)
        # sc: O(node)
        heap = [(0, k)]
        
        # Dictionary to track shortest known time to each node
        # Invariant: once a node is added here, its shortest time is finalized
        shortest_time = {}
        
        # tc: each node/edge O(e) processed via O(log n) heap operations O(e log n)
        while heap:

            # Pop node with smallest known arrival time
            time, node = heapq.heappop(heap)
            
            # Skip if this node already has a finalized shortest time
            # (We found a better path earlier)
            if node in shortest_time:
                continue
            
            # Record shortest time to reach this node
            shortest_time[node] = time
            
            # Explore Choices:
            # Relax all outgoing edges from this node
            for neighbor, wt in graph[node]:

                # If neighbor not finalized, push updated time candidate
                if neighbor not in shortest_time:
                    heapq.heappush(heap, (time + wt, neighbor))
        
        # After processing:
        # If not all nodes were reached, signal cannot reach everyone
        if len(shortest_time) != n:
            return -1
        
        # Result:
        # The total network delay is the maximum shortest arrival time
        res = max(shortest_time.values())

        # overall: tc O(e log n)
        # overall: sc O(n + e)     
        return res

    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        
        # Why Dijkstras + MinHeap?
        # Dijkstras finds shortest path from a source node to all other nodes
        # in a weighted graph with non-negative edge weights, our case
        
        # Cell -> Node
        # Effort (absolute height difference) -> Weight
        # MinHeap ensures we always explore next cell with minimal effort first
        # Guarantees the minimum maximum effort path to the bottom-right cell.
        
        # Note:
        # 1. Use MinHeap to track cells by minimal effort seen so far
        # 2. Effort to reach a cell -> max(absolute difference along path)
        # 3. Track visited/effort for each cell
        # 4. Pop cell with lowest effort from heap, update neighbors
        # 5. Stop when reaching bottom-right cell
        # Result -> path of lowest effort

        rows, cols = len(heights), len(heights[0])
        efforts = [[float('inf')] * cols for _ in range(rows)]
        efforts[0][0] = 0

        # (effort, row, col)
        min_heap = [(0, 0, 0)]
        directions = [(0,1),(1,0),(-1,0),(0,-1)]

        while min_heap:
            curr_effort, r, c = heappop(min_heap)

            # Reached target -> bottom right
            if r == rows - 1 and c == cols - 1:
                return curr_effort

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    next_effort = max(curr_effort, abs(heights[r][c] - heights[nr][nc]))
                    if next_effort < efforts[nr][nc]:
                        efforts[nr][nc] = next_effort
                        heappush(min_heap, (next_effort, nr, nc))

        # default, though problem guarantees a path exists
    
        # overall: time complexity O(R*C*log(R*C)) due to heap operations
        # overall: space complexity O(R*C) for effort tracking and heap
        return 0

    def swimInWater(self, grid: List[List[int]]) -> int:
        
        # Why Dijkstras + MinHeap? 
        # Cell -> Node
        # Weight -> determined by max elevation along path so far
        # Dijkstras algo finds path from source (0,0) to target (n-1,n-1)
        # that minimizes the max elevation
        # MinHeap ensures we always expand the path with lowest current
        # maximum elevation
        # Guarantees minimum time t
        # Result -> path of minimum height
        
        # Note:
        # 1. We want min time t to reach (n-1, n-1)
        # 2. At any step, t = max elevation along the path
        # 3. Use min-heap to always expand the path with lowest t so far
        # 4. Track visited cells to avoid revisiting

        n = len(grid)
        visited = [[False] * n for _ in range(n)]
        
        # (time_so_far, row, col)
        min_heap = [(grid[0][0], 0, 0)]
        directions = [(0,1),(1,0),(-1,0),(0,-1)]

        while min_heap:
            t, r, c = heappop(min_heap)
            if visited[r][c]:
                continue
            visited[r][c] = True

            # Reached target cell
            if r == n - 1 and c == n - 1:
                return t

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:

                    # time to reach neighbor = max(current path t, neighbor elevation)                    
                    heappush(min_heap, (max(t, grid[nr][nc]), nr, nc))

        # default, problem guarantees a path exists
        
        # overall: time complexity O(n^2 * log(n^2)) due to heap operations
        # overall: space complexity O(n^2) for heap and visited
        return 0

    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        
        # Modified Disjkstras?
        # Modified for graphs with 'stops' constraint
        # Each node in heap is (stops_so_far, current_node, cost_so_far)
        # MinHeap guarantees we expand path with lowest cost so far
        # Only continue paths that respect the stops limit (<= k)
        
        # Build adjacency list
        adj={i:[] for i in range(n)}
        for u,v,w in flights:
            adj[u].append((v,w))

        # Initialize distance array and min-heap
        dist=[float('inf')]*n
        dist[src]=0
        q=[]
        
        # (stops_so_far, current_node, cost_so_far)
        heapq.heappush(q,(0, src, 0))

        # Process heap
        while q:
            stops,node,wei=heapq.heappop(q)

            # Skip if stops exceed limit
            if stops>k:
                continue

            # Explore neighbors 
            for nei,w in adj[node]:
                next_cost = cost + w

                # Only push if we improve distance
                if dist[nei]>next_cost and stops<=k:
                    dist[nei]=next_cost
                    heapq.heappush(q,((stops+1,nei,next_cost)))
        print(dist)

        # Check if destination reachable
        if dist[dst]==float('inf'):
            return -1

        res = dist[dst]

        # overall: time complexity O(E log N) in practice, E = # of edges
        # overall: space complexity O(N + E) for adjacency list and heap    
        return res