Registered order can you explain a bit..
An other geeks and people.... what happened ?? reply 2012/4/20 Registered user <[email protected]> > i think if u mark the path which u want to block as visited beforehand > then u may get it, m not sure but i think it should work. > > or if possilbe give the sample input / output cases , den i may solve > it.... > > On 4/20/12, Andrey Ponomarev <[email protected]> wrote: > > Hypothesis 1: after eliminating one edge e' the shortest path from a > > to b must contain vertex v, such that > > neighter sp(a,v), nor sp(v,b) contain e' in the original graph, if > > there is such. (Here sp stands for 'shortest path') > > Hypothesis 2: if v is some vertex of the modified graph, such that > > neighter sp(a,v), nor sp(v,b) contain e' in > > the original graph, the shortest path from a to b in the modified > > graph is len(sp(a,v)) + len(sp(v,b)). > > > > If both hypotheses are true then you may try following. In the > > original graph build 2 shortest path trees: > > one from a and one from b with edges reversed. The first tree let you > > at O(1) find len(sp(a,v)), аnd > > the second let you at O(1) find len(sp(v,b)). When you have an edge > > (v1, v2) removed you should walk > > tree1 from v2 and tree2 from v1 and mark all vertices you pass by. > > Then you should find one unmarked > > vertex with the minimum sum of len(sp(a,v)) + len(sp(v,b)) - it will > > be the shortest path and it took O(n). > > > > 20 апреля 2012 г. 10:48 пользователь vivek dhiman > > <[email protected]> написал: > >> ok.. > >> So if an edge is removed from existing path.Do i have to again find the > >> shortest path ? > >> > >> > >> On Fri, Apr 20, 2012 at 11:08 AM, Luke Pebody <[email protected]> > >> wrote: > >>> > >>> 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. > >> > >> > >> > >> > >> -- > >> 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. > > > > > > -- > 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. > > -- 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.
