Помогите с задачкой,не могу въехать Условие Дорожное движение в городе Дингилвилле устроено необычным образом. В городе есть перекрестки и дороги, которыми перекрестки связаны между собой. Любые два перекрестка могут быть связаны не более чем одной дорогой. Не существует дорог, соединяющих один и тот же перекресток с самим собой. Время проезда по дороге в обоих направлениях одинаково. На каждом перекрестке находится один светофор, который в каждый момент времени может быть либо голубым, либо красным. Цвет каждого светофора изменяется периодически : в течение некоторого интервала времени он голубой, а затем, в течение некоторого другого интервала - красный. Движение по дороге между любыми двумя перекрестками разрешено тогда и только тогда, когда светофоры на обоих перекрестках этой дороги имеют од ин и тот же цвет в момент въезда на эту дорогу. Если транспортное средство прибывает на перекресток в момент переключения светофора, то его поведение будет определяться новым светом светофора. Транспортные средства могут находиться в состоянии ожидания на перекрестках. У Вас есть карта города, которая показывает: · время прохождения каждой дороги (целые числа). · длительность горения каждого цвета для каждого светофора (целые числа). · начальный цвет и оставшееся время горения этого цвета (целые числа) для каждого светофора. Вы должны определить путь между двумя заданными перекрестками, позволяющий транспортному средству проехать от начального перекрестка к конечному за мимнимальное время с момента старта. Если существуют несколько таких путей, то Вы должны вывести только один из них. Ограничения · 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
jones Здесь вполне можно использовать алгоритм Дейксты, зная минимальное время, когда мы можем попасть в некоторую вершину, считаем сколько времени нужно ждать чтобы проехать по некоторой дороге, прибавляем время в дороге, и смотрим получилось у нас попасть в соседнюю вершину быстрее или нет. В общем самое интересное тут это функция, которая для двух светофоров и некоторого начального момента, скажет когда в ближайшем времени светофоры будут в одинаковом состоянии.
Эм... да... можно... чё-то решил, что временная зависимость длины ребра графа, будет для Дейкстры проблемой... P.S. Точнее временная зависимость и была бы проблемой, если бы она была произвольной.
Гы Вот не знал, что это оказывается задача с IOI: http://acm.sgu.ru/problem.php?contest=0&problem=103 Ну а по самой задаче - да, конечно, Дейкстра.
Black_mirror,я что-то не понимаю,что интересного в функции, которая для двух светофоров и некоторого начального момента, скажет когда в ближайшем времени светофоры будут в одинаковом состоянии.
