3243.新增道路查询后的最短距离I

链接：3243.新增道路查询后的最短距离I
难度：Medium
标签：广度优先搜索、图、数组
简介：返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。

题解 1 - python

• 编辑时间：2024-11-19
• 执行用时：421ms
• 内存消耗：16.93MB
• 编程语言：python
• 解法介绍：bfs

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        res = []
        next = [[i + 1] for i in range(n - 1)]
        for v1, v2 in queries:
            next[v1].append(v2)
            q = deque([0])
            used = set([0])
            size = 1
            step = 0
            while q:
                node = q.popleft()
                if node == n - 1:
                    res.append(step)
                    break
                for child in next[node]:
                    if child not in used:
                        used.add(child)
                        q.append(child)
                size -= 1
                if size == 0:
                    size = len(q)
                    step += 1
        return res