|
|
|
|
|
|
|
| 1 Алемхан Касиман, 14 февраля 2022 г. 6:07:21 |
| странно, дейкстра прошла
|
|
|
| 2 Рамазанов Айтым Нурмбетович, 29 октября 2015 г. 0:17:23 |
| Долго ломал я голову над тем, каким алгоритмом решил я задачу. Не Декстера, не Форд-Беллман. Идея алгоритма оказалась похоже на алгоритм Флойда-Уоршелла. Вкратце алгоритм делает следующее: при считывании очередного "короткого" ребра (b, e) заново обновляется весь массив длин, при этом не забываем проверять на достижимость вершины. Алгоритм очень неэффективный (грубо говоря m*n*n итерации), но зато несложный. До этого не знал ни один из трех алгоритмов. Зато теперь приму на вооружение эти алгоритмы
|
|
|
| 3 Евгений Сибиль, 25 сентября 2015 г. 15:02:18 |
Админы, ну зачем вы так? В третьем тесте n и m записаны на разных строчках.
Сделайте, пожалуйста, по-нормальному, фиксированный формат. Мы же алгоритмы реализуем, а не играем в игру "угадай, как записаны данные". В питоне, например, данные считываются по строкам, и потом разбираются, а если вы записываете их как левой ноге захочется - становится непонятно, где падает и почему.
|
|
|
| 4 Филипп Кофман Олегович, 26 марта 2012 г. 10:39:02 |
Тесты графов с наличием отрицательных циклов есть??
Нет. В третьем предложении условия задачи написана правда. Условиям задач можно верить. А иначе как их решать?
|
|
|
| 5 Франчук Роман Павлович, 17 марта 2010 г. 12:39:03 |
| Нет нельзя. Дейкстра не умеет работать с ребрами с отрицательным весом. Можно Флойдом, но неэффективно.
|
|
|
| 6 Березин Дмитрий Андреевич, 07 марта 2010 г. 13:28:22 |
| Эту задачу можно решить Дейкстрой?
|
|
|
| 7 Коншин Андрей Сергеевич, 16 декабря 2009 г. 20:21:17 |
е мое....еще бы 200 лет думал че за фигня и почему не может пройти.....пока не почитал еще раз условие и не посмотрел пробный тест......из i в j может быть несколько ребер.....нужно выбирать минимальное))) а в первом тесте минимальное ребро из 2 в 3 вершину стоит последним..вот почему работает))
|
|
|
| 8 Барышев Валентин Валерианович, 27 октября 2009 г. 11:46:27 |
a в ответе первое число всегда 0 или оно может быть разным?
всегда 0. ведь это наикратчайший путь из 1й вершины в 1ю вершину.
|
|
|
| 9 Шипелов Роман Борисович, 11 марта 2009 г. 0:17:03 |
у вас ошибка в примере: ребру 2-->3 приписаны два раных веса
это как раз хорошо, лучше позволяет понять задачу.
|
|
|
| 10 Artem, 02 июля 2008 г. 23:57:16 |
Подскажите где можно взять нормальный разбор этого алгоритма. ХОРОШЕЕ ОПИСАНИЕ, А НЕ САМО РЕШЕНИЕ
Надеюсь, что когда-нибудь на этом сайте в разделе "Курс олимпиадников", но там до графов мне еще далеко...
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
