Дистанционная подготовка: Флойд - Задача C. Самый короткий путь
Флойд - Задача C. Самый короткий путь
от Игорь Беляев - Понедельник 4 Август 2008, 14:49
  День добрый!

Не могу почему-то справится с этой задачей, все время получаю WA#1.
Суть решения - запускаем обычный алгоритм Флойда. При наличии цикла отрицательного веса(ЦОВ) выводим -1, при его отсутсвии находим минимальный элемент в матрице кратчайших путей (МКП) между вершинами. ЦОВ определяю следующим образом: Если в МКП на главной диагонали есть отрицательный элемент, то цикл есть, иначе нет).

ну вот собственно и все. Мой исходник лежит тута http://www.everfall.com/paste/id.php?hi0mxmtgf8vj

Остается еще вот такой вопрос: если МКП будет равен -1, то ответ на задачу можно понимать двояко: толи есть ЦОВ, то ли МКП равен -1... но думаю это не суть важно)
Re: Флойд - Задача C. Самый короткий путь
от Андрей Шестимеров - Среда 6 Август 2008, 14:39
  Требуется найти самый короткий путь между двумя различными городами