4 0 0 0 0 0 Edited by author 23.05.2007 21:03 thanks, buddy it helped me What may be the test 54 ?? Edited by author 29.08.2016 21:00 I tried all the samples from the discussion and I tried some exception conditions. The program works for all these samples. Do you have any idea what can be wrong? I can share my C++ code. Tried disconnected graphs, individual nodes, just a path, and zero edge and node weights. It works for all of the cases :/ can anybody give some cases? what the #8 is? 9 8 1 5 4 6 10 1 2 2 1 1 2 1 2 3 10 2 4 1 4 5 1 4 6 2 6 7 2 6 8 3 3 9 1 Answer: 39 5 5 4 3 2 9 or 39 5 9 2 3 4 5 Answer: 39 5 5 4 2 3 9 or 39 5 9 3 2 4 5 Edited by author 09.12.2013 11:44 I am getting TLE on test 24. How will you choose from which town to start? Because of this I had to start from every town to find the answer. For each town it took me O(n),so for all the towns it becomes O(n^2), causing TLE. Actually that's the main issue for this problem. If you want a hint  that's it: try to develop some dynamic programming scheme for solution. Edited by author 05.04.2013 16:20 Edited by author 05.04.2013 16:20 Finally AC! Slight implementation change got me AC!. Edited by author 05.04.2013 16:19 Edited by author 05.04.2013 16:19 No DP! Just 2 BFS for each connected component. try this test: 3 2 0 0 1 1 2 1 1 3 1 answer is 3 3 3 1 2 Edited by author 15.01.2010 22:22 please give hint about test # 3 i decompose graph into connected components (by one dfs) after that i count diameter of each component(by one special_dfs) and refresh global_variable if need. my programm works at all my tests and sample test too. What is the test #29? Can anybody give me test for WA #29??? Will anybody answer my question??? Will anybody answer my question??? Maybe in year or two. Forum is not for instant answers. It is rather knowledge base. There is no answer to your question in the base yet. Maybe answer will appear but 99% that _you_ will first find the bug and post yourself test for the bug here than someone get wa29 and post test for it. At last, I've solved it)))) If you have WA29 try this test: 8 6 1 2 5 4 1 2 1 6 1 2 1 2 3 1 2 4 1 5 6 1 6 7 1 6 8 1 Answer is : 13 3 3 2 4 I have WA #29. At first i thought that it is simple overflow, but it is not right. Read problem statement more closely. The graph can be disconnected. What about this test? maybe there isolated node? some like this 3 1 100 50 10 2 3 10 Edited by author 14.08.2008 23:02 I have tried for many times but always WA#29 Could you please tell me why? As I understood there is vertex with number "0" and what is happiness of town "0" ? I believe you've got the problem statement wrong, vertexes are numbered from 1 to N, so there is no town with number 0. autors must add this restriction in Statement of the problem K is bounded by this condition: "It turned out that if Petrovich can fly (using one or several flights) from town i to town j, then there is exactly one way to do this" sample #2 why he doesn't fly from 8 to 4? Here a part of my program:  const maxn = 50000; var gr : array[1..maxn, 1..maxn] of Integer; maxy : array[1..maxn] of Longint; c : array[1..maxn] of boolean; path : array[1..maxn] of Longint; d : array[1..maxn] of Longint; a : array[1..maxn] of Integer; vs : array[1..maxn] of Longint; que : array[1..maxn] of Longint; first, last : Longint; n, k, i, j, x, y, w, tmp, max, start, finish, u, v : Longint; stop : boolean;  When maxn = 500, I have WA#9. When maxn = 20000, I have Crash (access violation) #9. When maxn > 20000, sometimes I have ML #1 (But memory isn't shown!), sometimes I have Crash (access violation) #1. What does it mean? Edited by author 29.08.2006 02:57 you can't use O(N^2) memory. it's ML N^2*(1 byte)= 2.5GB Edited by author 29.08.2006 20:30 
