You may find the ideas in http://www.eecs.harvard.edu/~parkes/cs286r/spring02/papers/vickrey.pdf interesting.
On May 17, 2:44 pm, vivek dhiman <[email protected]> wrote: > Please help me solve this problem for cases with high number of nodes. I am > getting time limit exceeded. > > Ms.Kox enjoys a nice job of her interest, but she does not like to waste > much time on going-to/coming-from office. She is now aware of the route to > her office that has the smallest distance, after all she has been working > there for past five years. > > The recent maintenance of roads that has started is an issue now. Every day > a road gets blocked because of the maintenance and no one can use it that > day( however all other roads can be used). You are her new intern and this > task is for you. You need to determine for each day the minimum distance > that she has to travel to reach her office. > > *Input Format:* > > There are N cities numbered 0 to N-1 and M bidirectional roads. > First line of the input contains two integers N and M. > Then follows M lines each containing three space-separated integers u , v > and w, which means that there is a bi-directional road connecting city u > and city v , and w is the length of this road.There is at most one road > between any two cities and no road connects a city to itself. > Next line contains two integers S and D, S is the city in which Mr. Kox > lives and D is the city in which her office is located. > Next line contains an integer Q, the number of queries. > Then follows Q lines each containing two integers u and v , which tells > that the road between city u and city v is blocked on that day. > > *Output Format:* > > Q lines , each line containing minimum distance Ms.Kox has to travel on > that day.If there is no path print *"Infinity"* (quotes for clarity). > > *Constraints:* > 0 < N < 200,000 > 0 < M < 200,000 > 0 < Q < 200,000 > 0 <= S , D < N > > *Sample input:* > > 6 9 > 0 1 1 > 1 2 1 > 2 3 1 > 3 4 1 > 4 5 1 > 2 4 5 > 3 5 8 > 1 3 3 > 0 2 4 > 0 5 > 9 > 0 1 > 1 2 > 2 3 > 3 4 > 4 5 > 2 4 > 3 5 > 1 3 > 0 2 > > * > * > > *Sample output :* > > 7 > 6 > 6 > 8 > 11 > 5 > 5 > 5 > 5 > > * > * -- 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.
