Leetcode 3243. Shortest Distance After Road Addition Queries I

• Leetcode 3243. Shortest Distance After Road Addition Queries I
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3243. Shortest Distance After Road Addition Queries I

1. 解题思路

这一题我做的比较暴力，就是动态规划，然后由于图一直在更新，所以加了一个tag来注明版本，然后进行处理。

算是勉强过了所有测试样例吧……

2. 代码实现

给出python代码实现如下：

class Solution:def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:graph = {i: [i+1, ] for i in range(n-1)}@lru_cache(None)def dfs(u, tag):if u == n-1:return 0return 1 + min(dfs(v, tag) for v in graph[u])ans = []for i, (u, v) in enumerate(queries):graph[u].append(v)ans.append(dfs(0, i))return ans

提交代码评测得到：耗时4639ms，占用内存53.7MB。