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

今天看到很有意思的一个题目，记录下来，供大家参考

题目描述

解题思路

为了解决这个问题，我们需要处理一系列的单向道路添加操作，并在每次添加后计算从城市 0 到城市 n-1 的最短路径长度。由于初始时每个城市 i 都有一条到 i+1 的单向道路，所以初始的最短路径长度就是 n-1（直接沿着这条链走）。

然而，当我们添加新的单向道路时，可能会缩短这个路径。为了高效地处理这些更新和查询，我们可以使用并查集（Union-Find）数据结构来维护城市之间的连通性和路径长度。但是，由于并查集通常不直接支持查询两点之间的最短路径长度，我们需要稍微修改一下这个数据结构或结合其他方法来达到目的。

然而，在这个特定的问题中，我们可以采用一种更简单但可能不是最优解的方法：使用图的遍历（如 Dijkstra 算法或 Floyd-Warshall 算法）来在每次添加新边后重新计算最短路径。由于题目中的 n 和 queries 的大小限制可能允许这种方法的实现（尽管可能不是最高效的），我们可以选择实现这种方法。

但考虑到实现的复杂性和效率，我将给出一个基于简单图遍历（而非完全优化的算法）的解答框架。对于更高效的解决方案，可能需要使用更复杂的图算法和数据结构。

下面是一个基于每次查询后重新计算最短路径的 Python 示例代码：

def find_shortest_path(n, queries):# 初始化图，由于初始时只有 i 到 i+1 的路，这里我们实际上不需要显式存储# 但为了处理查询，我们可以使用一个邻接表来存储图graph = [[] for _ in range(n)]for i in range(n - 1):graph[i].append(i + 1)def dijkstra(start):# 简单的 Dijkstra 实现distances = [float('inf')] * ndistances[start] = 0visited = [False] * nfrom heapq import heappop, heappushpriority_queue = [(0, start)]while priority_queue:current_distance, current_node = heappop(priority_queue)if visited[current_node]:continuevisited[current_node] = Truefor neighbor in graph[current_node]:distance = current_distance + 1if distance < distances[neighbor]:distances[neighbor] = distanceheappush(priority_queue, (distance, neighbor))return distances[-1]  # 返回从 start 到 n-1 的最短距离result = []for query in queries:u, v = query# 添加新边graph[u].append(v)# 重新计算最短路径shortest_path_length = dijkstra(0)result.append(shortest_path_length)return result# 示例
n = 5
queries = [[2, 3], [1, 4], [3, 1], [0, 4]]
print(find_shortest_path(n, queries))

注意：上述代码中的 Dijkstra 算法实现是为了简化问题而设计的，并没有进行过多的优化。在实际应用中，对于频繁更新和查询的图，可能需要考虑使用更高效的图算法和数据结构，如动态图算法或增量式最短路径算法。

此外，如果 n 和 queries 的规模非常大，上述方法可能会因为重复计算而效率较低。在这种情况下，可以考虑使用更高级的数据结构或算法，如使用边松弛技术结合优先队列来优化 Dijkstra 算法，或者考虑使用 Floyd-Warshall 算法（尽管其时间复杂度较高，但可以在常数时间内回答任意两点间的最短路径查询）。