Here's a start for you. Find the shortest route. This works as an answer if you remove any edge not in that route. Now you just have to solve it for any removed edges that are in that route.
On 20 Apr 2012, at 05:19, vivek dhiman <[email protected]> wrote: > Hi all geeks > > So I have a simple question. > > Suppose you have a graph G(V,E). > You are supposed to find the shortest path from a vertex 's' to vertex 'e' > for 'n' different cases. > > In each case one of the edges 'Ei' (any one edge) of the graph will be > blocked/deleted only for that case and we have to find the shortest path in > the graph with that edge removed. > > Guys finding the shortest path is easy. But how can I make the algo so fast > that even if I remove one of the edges my algo should still be very fast. O(n > log n) or faster. > Remember we are not deleting the edges permanently. We are just temporary > removing one edge per case. > In each case only one edge is removed. > Suppose we blocked one edge E in one case. We have to find the shortest path > for the graph. > In next case, we will reconnect the last edge and we will block/remove a new > edge. And again for this new case we have to find the shortest path. > > Another way of understanding the problem is suppose there are cities > connected to each other. > And every day one of the roads gets blocked because of heavy rain. what is > the shortest path every day from city s to e. > Also one more important thing to note that each road can be used only once. > But there could be more than 1 direct road from city a to city b. > > FInd the shortest path distance from city s to e on a day when all direct > roads from city f to city h are blocked. If there is no connecting path > return -1 > > Thanks and Regards > Vivek Dhiman > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
