Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 08.04.2010, 16:31
Новичок

Отправить личное сообщение для LGod Посмотреть профиль Найти все сообщения от LGod
 
Регистрация: 08.04.2010
Сообщений: 14

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

 
Сообщений: n/a

Сообщение от LGod Посмотреть сообщение
Есть N городов, между которыми едут автобусы и действует воздушное соединения(в обох направлениях). Между любыми двумя городами проложено не более чем по одному рейсу каждого из типов. Продолжительность каждого из рейсов известна и одинакова в обе стороны. Нужно найти кратчайшое расстояния из одного города в другой, если авиарейсов в пути должно быть не больше чем M.
От последнего ограничения избавляемся расширением графа до N(M+1) вершин - каждая вершина в нем пара (город, число использованных авиарейсов). И в нем ищем пути какими-нибудь стандартными методами.
  #3  
Старый 08.04.2010, 19:19
Новичок

Отправить личное сообщение для LGod Посмотреть профиль Найти все сообщения от LGod
 
Регистрация: 08.04.2010
Сообщений: 14

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра
Комбинированный вид Комбинированный вид


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите решить задачу. Loonar Графы 10 12.12.2010 15:42
Помогите решить задачу по VB 6.0 гость Реализация, исходники, языки 1 03.10.2009 23:56
Помогите решить задачу !!!!!!! Glamour Задачи 2 19.03.2008 16:42
Помогите решить задачу Misha1 Математические алгоритмы (другое) 2 10.09.2007 01:44
помогите решить задачу Annet Оффтопик 0 16.12.2006 16:58