Алгоритмы, методы, исходники / Форум

Алгоритмы, методы, исходники / Форум (http://forum.algolist.ru/)
-   Графы (http://forum.algolist.ru/algorithm-graph/)
-   -   Помогите решить задачу с взвешенным графом. (http://forum.algolist.ru/algorithm-graph/3722-pomogite-reshit-zadachu-s-vzveshennym-grafom.html)

LGod 08.04.2010 16:31

Помогите решить задачу с взвешенным графом.
 
Есть N городов, между которыми едут автобусы и действует воздушное соединения(в обох направлениях). Между любыми двумя городами проложено не более чем по одному рейсу каждого из типов. Продолжительность каждого из рейсов известна и одинакова в обе стороны. Нужно найти кратчайшое расстояния из одного города в другой, если авиарейсов в пути должно быть не больше чем M.

гость 08.04.2010 16:36

Цитата:

Сообщение от LGod (Сообщение 11809)
Есть N городов, между которыми едут автобусы и действует воздушное соединения(в обох направлениях). Между любыми двумя городами проложено не более чем по одному рейсу каждого из типов. Продолжительность каждого из рейсов известна и одинакова в обе стороны. Нужно найти кратчайшое расстояния из одного города в другой, если авиарейсов в пути должно быть не больше чем M.

От последнего ограничения избавляемся расширением графа до N(M+1) вершин - каждая вершина в нем пара (город, число использованных авиарейсов). И в нем ищем пути какими-нибудь стандартными методами.

LGod 08.04.2010 19:19

Спасиба за подсказку


Часовой пояс GMT +4, время: 09:04.