3244.新增道路查询后的最短距离II

链接：3244.新增道路查询后的最短距离II
难度：Hard
标签：贪心、图、数组、有序集合
简介：返返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。

题解 1 - python

• 编辑时间：2024-11-20
• 执行用时：79ms
• 内存消耗：44.22MB
• 编程语言：python
• 解法介绍：贪心，考虑到不会交叉的路径，尽可能选择新连接的路径即可

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        res = []
        arr = [i + 1 for i in range(n)]
        cur = n - 1
        for n1, n2 in queries:
            if 0 < arr[n1] < n2:
                v = 0
                walker = n1
                while walker != n2:
                    v += 1
                    arr[walker], walker = 0, arr[walker]
                cur -= v - 1
                arr[n1] = n2
            res.append(cur)
        return res