> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Shortest Distance After Road Addition Queries

> Tested Python solution for LeetCode 3243 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 3243, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Breadth-First Search](/catalog/topics/breadth-first-search), [Graph Theory](/catalog/topics/graph-theory). [View on LeetCode](https://leetcode.com/problems/shortest-distance-after-queries-i/description/).

Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 3243   # by problem number
lcpy gen -s shortest_distance_after_queries_i   # by problem name
```

## Problem

You are given an integer \<code>n\</code> and a 2D integer array \<code>queries\</code>.

There are \<code>n\</code> cities numbered from \<code>0\</code> to \<code>n - 1\</code>. Initially, there is a \<strong>unidirectional\</strong> road from city \<code>i\</code> to city \<code>i + 1\</code> for all \<code>0 \<= i \< n - 1\</code>.

\<code>queries\[i] = \[u\<sub>i\</sub>, v\<sub>i\</sub>]\</code> represents the addition of a new \<strong>unidirectional\</strong> road from city \<code>u\<sub>i\</sub>\</code> to city \<code>v\<sub>i\</sub>\</code>. After each query, you need to find the \<strong>length\</strong> of the \<strong>shortest path\</strong> from city \<code>0\</code> to city \<code>n - 1\</code>.

Return an array \<code>answer\</code> where for each \<code>i\</code> in the range \<code>\[0, queries.length - 1]\</code>, \<code>answer\[i]\</code> is the length of the shortest path from city \<code>0\</code> to city \<code>n - 1\</code> after processing the \<strong>first\</strong> \<code>i + 1\</code> queries.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2024/06/28/image8.jpg)

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

![Example 1](https://assets.leetcode.com/uploads/2024/06/28/image9.jpg)

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

![Example 1](https://assets.leetcode.com/uploads/2024/06/28/image10.jpg)

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

![Example 2](https://assets.leetcode.com/uploads/2024/06/28/image11.jpg)

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

![Example 2](https://assets.leetcode.com/uploads/2024/06/28/image12.jpg)

After the addition of the road from 0 to 2, the length of the shortest path remains 1.

### Constraints

* \<code>3 \<= n \<= 500\</code>
* \<code>1 \<= queries.length \<= 500\</code>
* \<code>queries\[i].length == 2\</code>
* \<code>0 \<= queries\[i]\[0] \< queries\[i]\[1] \< n\</code>
* \<code>1 \< queries\[i]\[1] - queries\[i]\[0]\</code>
* There are no repeated roads among the queries.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/shortest_distance_after_queries_i/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/shortest_distance_after_queries_i/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
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
```

## Complexity

| Time | Space |
| - | - |
| O(n + q \* k) where k is the number of distance decreases, q = len(queries) | O(n + q) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.