Discussion @ 1421. Credit Operations @ Timus Online Judge

elmariachi1414 (TNU) Help (TLE #12, O(V*E^2)) [2] // Problem 1421. Credit Operations 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

Fyodor Menshikov Re: Help (TLE #12, O(V*E^2)) [1] // Problem 1421. Credit Operations 14 Jan 2007 22:07

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

elmariachi1414 (TNU) Re: Help (TLE #12, O(V*E^2)) // Problem 1421. Credit Operations 15 Jan 2007 22:52

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

Discussion of Problem 1421. Credit Operations