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

Online Judge

Задачи

Авторы

Соревнования

О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки

Архив задач
Отправить на проверку
Состояние проверки
Руководство

Регистрация
Исправить данные
Рейтинг авторов

Текущее соревнование
Расписание
Прошедшие соревнования
Правила

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

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

Послано elmariachi1414 (TNU) 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

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

Послано Fyodor Menshikov 14 янв 2007 22:07

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

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

Послано elmariachi1414 (TNU) 15 янв 2007 22:52

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