ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1004. Экскурсия

Did anyone get AC with O(n4) algo after redjudgement 15 Sep 2013
Послано sanok 16 июн 2014 14:10
I implemented the first idea came to my mind: for each connected vertices v1,v2 removing edge v1-v2 and finding shortest paths from v1 to v2 with Dijkstra. As for my estimations it should be O(edges^2) or O(vertices^4) for very connected graphs.

It was reported in other threads of this discussion that this solution should fit time limits, but mine does not pass test #3 (time limit exceed).

I am curious if solutions like mine now can be accepted. Did anyone have success with that approach after rejudgement in Sep 2013? Or now only O(v^3) solutions can pass all tests?

Thanks