C++ Алгоритм с возвратом

[Vitaliya_1619]

Доброго времени суток. Кто может помочь с задачкой:

По системе двусторонних дорог определить, определить есть ли в ней город, из которого можно добраться в любой другой менее чем за 100 км. Разрешается построить дополнительно 3 дороги.

Заранее большое спасибо!!! Очень выручите!))

[Stilet]

И как же описываются в задаче трассы и города?

[Poma][a]

Эм.. Что-то тут не так..

Разрешается построить дополнительно 3 дороги.

Эм.. Хорошо.. Три дороги из любого в любой? А длина их какая? Заведомо меньшая 100км?

[Serge_Bliznykov]

Сообщение от Poma][a

Эм.. Что-то тут не так..
Эм.. Хорошо.. Три дороги из любого в любой? А длина их какая? Заведомо меньшая 100км?

полностью согласен.
иначе достаточно построить всего одну дорогу из начального города в конечный длиной 99 км и всё, задача решена!

[Poma][a]

Сообщение от Serge_Bliznykov

полностью согласен.
иначе достаточно построить всего одну дорогу из начального города в конечный длиной 99 км и всё, задача решена!

Стоп! Нам нужно определить, есть ли город, из которого можно попасть из в любой город, причем этот путь не будет превышать 100км.
Про "конечный город" нет ни слова!

[Utkin]

и всё, задача решена!

Совсем не факт. Если у города нет связей с 6-ю городами (а вот кучка независимых графов), то достройка трех дорог может и не помочь. А вообще условие более чем мутно описано. Меня смущают двухсторонние дороги и

в любой другой менее чем за 100 км

Что это? Максимальная длина пути (то есть задача китайского почтальона) или максимальное расстояние между двумя городами (то есть алгоритм Флойда к примеру).

[Poma][a]

Меня смущают двухсторонние дороги

Каким образом? Неориентированный граф..

Что это?

из которого можно добраться в любой другой менее чем за 100 км

Вывод : это

максимальное расстояние между двумя городами (то есть алгоритм Флойда к примеру)

Флойд дает N^3
Я бы сказал, что длина не может быть отрицательной (что также следует из условия задачи), поэтому будем использовать Дейкстру (от O(n log n + m log n) до O(n^2)

[Utkin]

Тогда модернизация алгоритма Флойда под достройку дорог. Осталось еще понять как при достройке дорог между городами определяются расстояния...

из которого можно добраться в любой другой менее чем за 100 км

Хотя цитата все равно мутная. Из одного города до другого можно добраться (иногда) разными способами и это может быть длина пути, а не расстояние между городами. Потому к примеру нарисовав граф можно чесать по окружной дороге и за 80 км, хотя прямая есть на 50 км (а вот дорожные работы идут). То есть фактически расстояние между городами 50 км, а путь составит 80 (объезд через Мухосранск).

поэтому будем использовать Дейкстру

То без разницы, я просто пример привел, чтобы было на что опереться.

[Poma][a]

Хотя цитата все равно мутная. Из одного города до другого можно добраться (иногда) разными способами и это может быть длина пути, а не расстояние между городами. Потому к примеру нарисовав граф можно чесать по окружной дороге и за 80 км, хотя прямая есть на 50 км (а вот дорожные работы идут). То есть фактически расстояние между городами 50 км, а путь составит 80 (объезд через Мухосранск).

Если есть дорога, то работы на ней не ведутся.. Метеориты там не падают.. Пробок тоже нет.. Поэтому расстоянием будет 50 км.

[Аватар]

Метеориты там не падают.. Пробок тоже нет.. Поэтому расстоянием будет 50 км

Там блокпосты и не проедешь