Shortest Distance After Road Addition Queries

lcpy gen -n 3243   # by problem number
lcpy gen -s shortest_distance_after_queries_i   # by problem name

Input: n = 5, queries = [[2,4],[0,2],[0,4]]
Output: [3,2,1]
Explanation:

After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.

Input: n = 4, queries = [[0,3],[0,2]]
Output: [1,1]
Explanation:

After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.

from collections import deque


class Solution:
    # Time: O(n + q * k) where k is the number of distance decreases, q = len(queries)
    # Space: O(n + q)
    def shortest_distance_after_queries(self, n: int, queries: list[list[int]]) -> list[int]:
        adj: list[list[int]] = [[i + 1] for i in range(n - 1)]
        adj.append([])
        dist = list(range(n))
        result: list[int] = []

        for u, v in queries:
            adj[u].append(v)
            if dist[u] + 1 >= dist[v]:
                result.append(dist[n - 1])
                continue

            dist[v] = dist[u] + 1
            queue: deque[int] = deque([v])
            while queue:
                cur = queue.popleft()
                for nxt in adj[cur]:
                    if dist[cur] + 1 < dist[nxt]:
                        dist[nxt] = dist[cur] + 1
                        queue.append(nxt)
            result.append(dist[n - 1])

        return result