Shortest Path Queries between 2 Constant Nodes in the Absence of an Edge

Правка en1, от c___a_, 2017-10-18 21:32:15

We are given 2 nodes s and t, and M queries that have one edge that needs to be deleted [only for this query], and for each query you need to output the shortest path between s and t. Note that s and t do not change.

1 ≤ Number of Nodes ≤ 7000

1 ≤ Number of edges ≤ 50000

1 ≤ Number of queries ≤ 10000

I couldn't find anything over the internet. I was thinking of something along the walks of pre-computation on a Dijkstra tree/Shortest path tree but couldn't think of anything. Can someone please provide hints or an approach to this problem?

Теги dijkstra, #graph, shortest path

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский c___a_ 2017-10-19 13:49:54 39
en1 Английский c___a_ 2017-10-18 21:32:15 642 Initial revision (published)