java - 带更新的最短路径算法

Question

有N个城市，有M条双向公路与之相连，我必须找到两个固定城市A和B之间的最短路径。

但问题是有 Q 个查询，两个城市之间的路径被阻塞，我必须在每个 Q 个查询中找到最短路径。

我的蛮力算法的时间复杂度是 O(QNlogN)，这给了我超出时间限制的错误，请帮助我如何改进我的解决方案

伪代码:

for u in Q:
  cin>>a>>b;
graph[a][b] = graph[b][a] = INFINITY VALUE
dijkstra algorithm();
cout<<Distance[D]<<endl; 

Problem LINK

MY CODE Which Is giving me Time Limit Exceeded Error

请帮助我如何改进我的算法？

Answer 1

论文Vickrey Prices and Shortest Paths:What is an edge worth? by John Hershberger and Subhash Suri展示了如何在 O(NlogN+M) 时间内解决此问题，其中 N 是顶点数，M 是边数。

这允许您根据阻塞的道路预先计算 M 个答案，因此您可以在 O(1) 中回答每个查询，总复杂度为 O(NlogN+M+Q)。