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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 11.05.2010, 16:47
Algor

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

«Светофоры»
Нужно закодить на с++ с использованием оптимального алгоритма.

Условие
Дорожное движение в городе Дингилвилле устроено необычным образом. В городе есть перекрестки и дороги, которыми перекрестки связаны между собой. Любые два перекрестка могут быть связаны не более чем одной дорогой. Не существует дорог, соединяющих один и тот же перекресток с самим собой. Время проезда по дороге в обоих направлениях одинаково. На каждом перекрестке находится один светофор, который в каждый момент времени может быть либо голубым, либо красным. Цвет каждого светофора изменяется периодически : в течение некоторого интервала времени он голубой, а затем, в течение некоторого другого интервала - красный. Движение по дороге между любыми двумя перекрестками разрешено тогда и только тогда, когда светофоры на обоих перекрестках этой дороги имеют од ин и тот же цвет в момент въезда на эту дорогу. Если транспортное средство прибывает на перекресток в момент переключения светофора, то его поведение будет определяться новым светом светофора. Транспортные средства могут находиться в состоянии ожидания на перекрестках. У Вас есть карта города, которая показывает:

· время прохождения каждой дороги (целые числа).

· длительность горения каждого цвета для каждого светофора (целые числа).

· начальный цвет и оставшееся время горения этого цвета (целые числа) для каждого светофора.

Вы должны определить путь между двумя заданными перекрестками, позволяющий транспортному средству проехать от начального перекрестка к конечному за мимнимальное время с момента старта. Если существуют несколько таких путей, то Вы должны вывести только один из них.



Ограничения
· 2≤N≤300, где N - количество перекрёстков. Перекрёстки нумеруются целыми числами от 1 до N.

· 1≤M≤14 000, где M - количество дорог.

· 1≤Lij≤100, где Lij - время, необходимое для перемещения от перекрёстка i до перекрёстка j, используя дорогу, которая соединяет перекрёстки i и j.

· 1≤tiB, tiP≤100, где tiB и tiP - длительность горения красного и голубого цвета соответственно на перекрёстке i.

· 1≤riС ≤tiС, где tiС - оставшееся время свечения начального цвета С (C принадлежит {P, B}) на перекрёстке i.

Входные данные
Входные данные задаются в файле lights.inp.

· Первая строка содержит два числа: номер начального и номер конечного перекрёстка.

· Вторая строка содержит два числа: N и M.

· Следующие N строк содержат информацию об N перекрёстках. (i+2)-ая строка входного файла содержит информацию о перекрёстке i: Ci, riС, tiB, tiP, где Ci ('B' или 'P' - большие латинские буквы) - начальный свет светофора на перекрёстке i.

· Следующие M строк описывают M дорог. Каждая строка имеет вид: i,j, Lij, где i и j - номера перекрёстков, которые связывает эта дорога.



Выходные данные
Выходные данные записываются в файл lights.out.

Если путь существует:

· Первая строка должна содержать минимальное время, необходимое для достижения конечного перекрёстка из начального.

· Вторая строка должна содержать список перекрёстков, который соответствует найденному минимальному пути. Перекрёстки должны быть записаны в порядке их посещения. Первое целое должно быть номером начального перекрёстка, последнее - конечного.

Если путь не существует:

· Единственная строка должна содержать только целое число 0.



Пример входных данных


1 4

4 5

B 2 16 99

P 6 32 13

P 2 87 4

P 38 96 49

1 2 4

1 3 40

2 3 75

2 4 76

3 4 77



Пример выходных данных
127

1 2 4
 


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

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