Discussion @ 1421. Credit Operations @ Timus Online Judge

Help (TLE #12, O(V*E^2))

Posted by elmariachi1414 (TNU) 11 Jan 2007 04:47

I implemented O(V*E^2) and received TLE #12.
Please, give me any hint!

My program runs very slow (about 7 sec) on maximal test
100
10000 10000 10000 ...
10000 10000 10000 ...

Edited by author 11.01.2007 05:35

Re: Help (TLE #12, O(V*E^2))

Posted by Fyodor Menshikov 14 Jan 2007 22:07

Use O(V^3)
http://en.wikipedia.org/wiki/Relabel-to-front_algorithm

Re: Help (TLE #12, O(V*E^2))

Posted by elmariachi1414 (TNU) 15 Jan 2007 22:52

Thank you! I'll try to study this algo from CLR

Discussion of Problem 1421. Credit Operations