ok guys.. I have solved the problem. now out of 10 8 test cases are passing Still 2 more test cases are left. problem is in those two test cases number of unique queries are huge.. can some one help with this ?
On Sun, May 20, 2012 at 8:48 PM, Sumudu <[email protected]> wrote: > 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. > > -- 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.
