Обсуждение @ 1421. Кредитные операции @ Timus Online Judge

elmariachi1414 (TNU) Help (TLE #12, O(V*E^2)) [2] // Задача 1421. Кредитные операции 11 янв 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] // Задача 1421. Кредитные операции 14 янв 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)) // Задача 1421. Кредитные операции 15 янв 2007 22:52

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

Обсуждение задачи 1421. Кредитные операции