def dijkstra(graph, source):
        
        # 1. Initialize all distances to ∞
        # 2. Set source distance = 0
        # 3. Use MinHeap to always expand smallest distance node
        # 4. Relax edges (update neighbors if shorter path found)
        # 5. Continue until all nodes processed

        # Initialize distances
        distances = {node: float('inf') for node in graph}
        distances[source] = 0

        # MinHeap (priority queue)
        min_heap = []

        # Push all distances to minHeap
        heapq.heappush(min_heap, (0, source))  # (distance, node)

        # Tracking closed nodes
        visited = set()

        # Process nodes
        while min_heap:

            # Smallest distance node
            current_dist, node = heapq.heappop(min_heap)

            # Skip if already finalized
            if node in visited:
                continue

            # Close Node
            visited.add(node)

            # Relax edges
            for neighbor, weight in graph[node]:
                new_dist = current_dist + weight

                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    heapq.heappush(min_heap, (new_dist, neighbor))

        # Map of shortest path from source node to all nodes
        return distances

    def bellman_ford(edges, V, source):

        # Initialize distances
        dist = [float('inf')] * V
        dist[source] = 0

        # Relax all edges V-1 times
        for _ in range(V - 1):
            for u, v, w in edges:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        # Check for negative weight cycles
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                raise ValueError("Graph contains a negative weight cycle")

        return dist

    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        
        # Dijkstra's Algorithm (Single-Source Shortest Path):
        # Find the shortest time from node k signal to all nodes
        # Find minimum time for node k signal to reach all nodes in 
        # a directed weighted graph

        # Idea Greedy:
        #   - Greedily expand node with smallest current travel time using minHeap
        #   - Once a node is popped from the minHeap, its shortest time is finalized,
        #     because the weights are non negative

        # Graph Construction:
        # Build Adjacency List:
        # graph[u] = [(v, weight), ...]

        # 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.

        # Adjacency list storage: graph[src_node] = [(dest_node, weight), ...]
        # sc: O(E)
        graph = defaultdict(list)

        # iterate over and store edges   
        # tc: O(E)   
        # sc: O(E) 
        for u, v, w in times:
            graph[u].append((v, w))
        
        # minHeap:
        # Ensures we always explore the node with the smallest known travel time next
        # sc: O(V)
        minHeap = []

        # Append root for processing
        # tc: O(log V)
        heapq.heappush(minHeap, (0, k))
        
        # Invariant:
        # Tracks finalized shortest time to each node
        # Once a node enters shortest_time,
        # its minimum distance is guaranteed final, because graph is non-negative
        # sc: O(V)
        shortest_time = {}
        
        # Dijkstras Traversal (Greedy BFS)
        #   - each edge may be pushed into heap
        #   - heap operations cost log V
        # tc: O(E log V)
        while minHeap:

            # Grad node with smallest known arrival time
            # tc: O(log V)
            time, node = heapq.heappop(minHeap)
            
            # Skip finalized nodes:
            # if node has already been finalized
            # tc: O(1)
            if node in shortest_time:
                continue
            
            # New node encountered:
            # track final shortest time
            # tc: O(1)
            shortest_time[node] = time
            
            # Edge Relaxation Opportunity:
            # from new node, check if we can relax the neighbors
            # and find a shorter path by going through the new node
            # tc: O(V)
            for neighbor, wt in graph[node]:

                # Skip finalized nodes:
                # Only relax neighbor if time has not be finalized
                if neighbor not in shortest_time:

                    # Relaxing possible:
                    # Get time going through new node to its neighbor
                    
                    # Calculate the total time to reach the neighbor via current node
                    new_time = time + wt

                    # Push relaxed time to minHeap
                    # tc: O(log V)
                    heapq.heappush(minHeap, (time + wt, neighbor))
        

        # Final Validation:
        # if not all nodes were reached, signal cannot propagate everywhere
        # tc: O(1)
        if len(shortest_time) != n:
            return -1
        
        # Network delay:
        # The node with the longest path will be the last node to receive the signal,
        # and determine the total network delay time
        # tc: O(V)
        res = max(shortest_time.values())

        # overall: tc O(E log V)
        # overall: sc O(V + E)     
        return res

    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        
        # Dijkstra's Algorithm (Single-Source Shortest Path):
        # Dijkstras finds shortest path from a source node to all other nodes
        # in a weighted graph with non-negative edge weights

        # Node = cell (r, c)
        # Edge weight = |height difference| between adjacent cells
        # MinHeap ensures we always expand the cell with smallest effort first

        rows, cols = len(heights), len(heights[0])

        # Tracks minimum effort needed to reach each cell
        efforts = [[float('inf')] * cols for _ in range(rows)]

        # starting cell has 0 effort
        efforts[0][0] = 0

        # MinHeap stores: (current path's max effort, row, col)
        min_heap = [(0, 0, 0)]

        # Directions: up, down, left, right
        directions = [(0,1),(1,0),(-1,0),(0,-1)]

        # While we still have 
        while min_heap:

            # Grab current effort node
            curr_effort, r, c = heappop(min_heap)

            # Exit Case:
            # If we reached bottom right, this is minimum possible effort
            if r == rows - 1 and c == cols - 1:
                return curr_effort

            # Explore neighbors
            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                # Check bounds
                if 0 <= nr < rows and 0 <= nc < cols:

                    # Effort to reach neighbor = max(current path effort, edge weight)
                    height_diff = abs(heights[r][c] - heights[nr][nc])
                    next_effort = max(curr_effort, height_diff)

                    # Only update if we found a smaller effort path to neighbor
                    if next_effort < efforts[nr][nc]:
                        efforts[nr][nc] = next_effort
                        heappush(min_heap, (next_effort, nr, nc))

        # Default return (problem guarantees a path exists)

        # overall: tc O(R*C*log(R*C)) due to heap operations
        # overall: sc O(R*C) for effort tracking and heap
        return 0

    def swimInWater(self, grid: List[List[int]]) -> int:
        
        # Dijkstras + MinHeap (Single-Source Shortest Path):
        # Dijkstras finds shortest path from a source node to all other nodes
        # in a weighted graph with non-negative edge weights
        
        # 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)

        # Keep track of visited cells to avoid revisiting
        visited = [[False] * n for _ in range(n)]
        
        # MainHeap store tuple: (current_max_elevation, row, col)
        minHeap = [(grid[0][0], 0, 0)]

        # Directions for 4 way movement
        directions = [(0,1),(1,0),(-1,0),(0,-1)]

        # While we have ___
        while minHeap:

            # Pop the cell with the smallest current max elevation
            current_max, r, c = heappop(minHeap)

            # Skip already visited cells
            if visited[r][c]:
                continue

            # Mark cell as visited
            visited[r][c] = True

            # Exit Condition:
            # If we reached the bottom right, return current_max as minimum time
            if r == n - 1 and c == n - 1:
                return current_max

            # Explore Neighbors:
            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                # Check boundaries and whether neighbor is already visited
                if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:

                    # Calculate the max elevation along the path to neighbor
                    neighbor_max = max(current_max, grid[nr][nc])

                    # Push neighbor into heap for further exploration
                    heappush(minHeap, (neighbor_max, nr, nc))

        # Default return (problem guarantees a path exists)

        # overall: tc O(n^2 * log(n^2)) due to heap operations
        # overall: sc 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:
        
        # Dijkstras + MinHeap (Single-Source Shortest Path):
        # Dijkstras finds shortest path from a source node to all other nodes
        # in a weighted graph with non-negative edge weights

        # Modified Dijkstras For K stops:
        # Each node in the minHeap stores:
        #   (stops_so_far, current_node, cost_so_far)
        # MinHeap ensures we always expand the path with the lowest cost first
        # Only continue paths that respect the stop limit (<= k)
        
        # Build adjacency list
        adj={i:[] for i in range(n)}
        for u, v, w in flights:
            adj[u].append((v,w))

        # Distance array tracks minimum cost to reach each node
        dist = [float('inf')] * n
        dist[src] = 0

        # MinHeap stores tuples: (stops_so_far, current_node, cost_so_far)
        minHeap = []
        
        # (stops_so_far, current_node, cost_so_far)
        heapq.heappush(minHeap, (0, src, 0))

        # Process heap
        while minHeap:
            stops, node, cost = heapq.heappop(minHeap)

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

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

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

        # 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

    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        
        # Dijkstra Approach:
        # Treat each variable as a node.
        # Each equation a / b = k becomes an edge a->b with weight log(k) (to transform multiplication into addition)
        # Edge b->a has weight log(1/k)
        # Then shortest path in log-space sums weights, which corresponds to multiplying ratios in normal space.

        # Build graph
        # Graph representation: adjacency list with log weights
       # sc: O(E)
        graph = defaultdict(list)
        for (u, v), val in zip(equations, values):
            graph[u].append((v, math.log(val)))
            graph[v].append((u, math.log(1 / val)))

        res = []

        # Dijkstra Helper
        # tc: O((V + E) log V) per query
        # sc: O(V) for priority queue and distances
        def dijkstra(start, end):
            if start not in graph or end not in graph:
                return -1.0

            heap = [(0.0, start)]  # cumulative log weight, node
            visited = {}

            while heap:
                cum_log, node = heapq.heappop(heap)
                if node in visited:
                    continue
                visited[node] = cum_log

                # Found target
                if node == end:
                    return math.exp(cum_log)  # convert log back to product

                for nei, weight in graph[node]:
                    if nei not in visited:
                        heapq.heappush(heap, (cum_log + weight, nei))

            return -1.0

        # Process all queries
        # tc: O(Q * (V + E) log V)
        for u, v in queries:
            res.append(dijkstra(u, v))

        # overall tc: O(Q * (V + E) log V)
        # overall sc: O(V + E) for graph + O(V) heap
        return res

    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        
        # DFS Approach:
        # Treat each variable as a node in a directed graph.
        # An edge u -> v with weight w represents u / v = w.
        # To answer a query, traverse the graph from numerator to denominator multiplying weights along the path.

        # Graph Representation: adjacency list with weights
        # sc: O(E)
        graph = defaultdict(list)

        # Build graph
        # tc: O(E)
        for (u, v), val in zip(equations, values):
            graph[u].append((v, val))
            graph[v].append((u, 1 / val))

        # DFS Helper
        # tc: O(V + E) per query worst-case
        # sc: O(V) recursion stack
        def dfs(curr, target, visited, acc):
            if curr == target:
                return acc
            visited.add(curr)
            for nei, val in graph[curr]:
                if nei not in visited:
                    res = dfs(nei, target, visited, acc * val)
                    if res != -1.0:
                        return res
            return -1.0

        res = []
        for u, v in queries:
            if u not in graph or v not in graph:
                res.append(-1.0)
            else:
                visited = set()
                res.append(dfs(u, v, visited, 1.0))

        # overall tc: O(Q * (V + E))
        # overall sc: O(V + E) for graph + O(V) recursion stack
        return res

    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        
        # BFS Approach:
        # Similar to DFS, but traverse level by level.
        # Each node represents a variable, edges store division ratios.
        # BFS guarantees we find a path without recursion stack issues.

        # Graph representation
        # sc: O(E)
        graph = defaultdict(list)
        for (u, v), val in zip(equations, values):
            graph[u].append((v, val))
            graph[v].append((u, 1 / val))

        res = []

        # BFS Helper
        # tc: O(V + E) per query
        # sc: O(V) for queue + visited
        def bfs(start, end):
            if start not in graph or end not in graph:
                return -1.0
            queue = deque([(start, 1.0)])
            visited = set([start])
            while queue:
                node, acc = queue.popleft()
                if node == end:
                    return acc
                for nei, val in graph[node]:
                    if nei not in visited:
                        visited.add(nei)
                        queue.append((nei, acc * val))
            return -1.0

        for u, v in queries:
            res.append(bfs(u, v))

        # overall tc: O(Q * (V + E))
        # overall sc: O(V + E) for graph + O(V) queue
        return res

    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        
        # Union-Find Approach:
        # Each variable is a node with a parent.
        # Store the ratio of each node to its parent.
        # When performing union, maintain ratios along the path.
        # To answer a query, check if two variables share the same root and compute the ratio.

        parent = {}
        ratio = {}  # node -> value relative to parent

        # Find with path compression
        # tc: O(α(N))
        def find(x):
            if parent[x] != x:
                orig_parent = parent[x]
                parent[x] = find(parent[x])
                ratio[x] *= ratio[orig_parent]
            return parent[x]

        # Union two nodes with given value
        # tc: O(α(N))
        def union(x, y, val):
            if x not in parent:
                parent[x] = x
                ratio[x] = 1.0
            if y not in parent:
                parent[y] = y
                ratio[y] = 1.0
            root_x, root_y = find(x), find(y)
            if root_x != root_y:
                parent[root_x] = root_y
                ratio[root_x] = val * ratio[y] / ratio[x]

        # Build union-find structure
        for (x, y), val in zip(equations, values):
            union(x, y, val)

        res = []
        for x, y in queries:
            if x not in parent or y not in parent:
                res.append(-1.0)
            elif find(x) != find(y):
                res.append(-1.0)
            else:
                res.append(ratio[x] / ratio[y])

        # overall tc: O(E * α(N) + Q * α(N))
        # overall sc: O(N) for parent and ratio
        return res