Архив форума — История

Pawa 23.04.2004 00:53

Как ее решать?
Я пробовал сдать ее на timus.ru алгоритмом Дейкстры, но получил TL.
Мне кажется что наверное можно как то модифицировать поиск в ширину, чтобы он работал и на таком графе, но вот сделать это у меня пока не очень получается :(

Vladimir 23.04.2004 01:03

Надо писать модифицированный алгоритм Дейкстры (с использованием двоичной или k-ичной кучи). Он работает O(N*M*log(N*M)). А вообще, в форуме уже есть тема, посвещенная этой задаче (Обсуждение задач -> Грязь).

Pawa 23.04.2004 01:30

Vladimir:

Надо писать модифицированный алгоритм Дейкстры (с использованием двоичной или k-ичной кучи). Он работает O(N*M*log(N*M)).

В каком смысле модифицированный? Я и писал с кучей.. когда не прошло с довичной, написал с 8-оичной.. Может на timus.ru другие таймлимиты?

Vladimir:

А вообще, в форуме уже есть тема, посвещенная этой задаче (Обсуждение задач -> Грязь).

Спасибо, на заметил.