Certainly there exist O(N^2) algo, but I had fun solving this problem by O(N^3) in 0.546 sec.

Please, give me an email or icq num so we can communicate. I want to ask you a few questions.

My e-mail is gallnrs@yandex.ru

That only means that there are tests with large ammounts of edges.

Running time of my algo doesn't depend on quantity of edges (except time of reading), only on N. It's like Floyd algorithm.

My program solve it for O(n ^ 2). But the time more than 1.1 sec.


Edited by author 15.02.2007 21:45

Same thing here. O(N+M) works in 1.2 sec. Optimizing scanf to gets+strtok makes it 0.9 sec.