Is it possible to solve it in Java without any special tricks?
I got MLE #16 any time when I submitted it in Java. Of course, the same C++ code gets AC and uses 35 MB.

I think that it is not good when equal solutions get different verdicts. Am I right? Admins, maybe you should increase memory limit?

Edited by author 01.11.2010 10:11

Maybe you have problem with huge amount of strings while construct graph. std::string is mutable, but java.lang.String is immutable and you not call garbage collector for removing unnecessary copies. Java solution without strings require only 12MB http://acm.timus.ru/status.aspx?space=1&num=1806&author=38899

I used strings only for reading input (not too much memory), then I used arrays of byte to store numbers and longs to keep them in map.

Your 12 MB solution is too perfect :) Many other C++ solutions use about 40 MB and, rewritten in Java, they will be MLE. It means that C++ and Java are not equal in their opportunities for this problem. I don't like this. And you?

By the way, Saratov provides programmers 256 MB for each problem. Why Timus can not do the same?

Do not create the whole graph forward, just get the neighbours for the current vertex which is already removed from heap, this is the only trick :). I've got AC with standard java HashMap and PriorityQueue.

wont it give tl if each step you go through 50000 neighbours.
About n*n/2 in worth case

Each vertex has at most 135 neighbours.

ur right accepted. Thanks.
Thanks to KALO too for the help.