Дан город, как набор точек-перекрёстков и соединяющих их улиц(для каждой улицы дана её длина). К любому перекрёстку подходит как минимум 3 улицы. В городе есть светофоры. Каждый светофор горит либо красным, либо зелёным. Красным он горит t1 секунд, зелёный горит t2 секунд. Каждый светофор в начальный момент времени имеет состояние [red|green] и количество времени колторое это состояние ещё будет продолжаться, это количество больше 0 и меньше t1|t2 для состояний red|green соответственно. В город на перекрёсток A въезжает грузовик, он должен выехать в перекёстка B. Наёти минимальный путь, учитывая, что на красный свет грузовик не едет.

Для 1000 перекрёстков и 10000 улиц время работы программы ~60сек

Здравствуйте, adontz, Вы писали:

A>Дан город, как набор точек-перекрёстков и соединяющих их улиц(для каждой улицы дана её длина). К любому

Если отношение t1/t2 рационально, то можно забабахать динамику. В перекрестке хранится, в какое минимальное время приехал грузовик в случае, когда свет горел уже i секунд.

Здравствуйте, adontz, Вы писали:

A>Дан город, как набор точек-перекрёстков и соединяющих их улиц(для каждой улицы дана её длина). К любому перекрёстку подходит как минимум 3 улицы. В городе есть светофоры. Каждый светофор горит либо красным, либо зелёным. Красным он горит t1 секунд, зелёный горит t2 секунд. Каждый светофор в начальный момент времени имеет состояние [red|green] и количество времени колторое это состояние ещё будет продолжаться, это количество больше 0 и меньше t1|t2 для состояний red|green соответственно. В город на перекрёсток A въезжает грузовик, он должен выехать в перекёстка B. Наёти минимальный путь, учитывая, что на красный свет грузовик не едет.

A>Для 1000 перекрёстков и 10000 улиц время работы программы ~60сек

Состояние всех светофоров в городе есть периодическая функцая с периодом t1+t2.
Вначале простой случай, когда t1+t2 целое и времена за которые грузовик проезжает любую улицу целые. Рассматриваем город как (t1+t2)*n точек. Где каждая точка это перекресток в определенный момент времени ( лежащий от 0 до t1+t2 ). Обычным волновым алгоритмом находим путь.

Более сложный случай, когда числа действительные, оказывается не более сложен. Просто узлы надо добавлять динамически. Очевидно, грузовик в любой точке может оказаться сколько угодно раз. Тогда запретим грузовику заезжать на перекрестки где он уже был более чем t1+t2 секунд назад. А возможно это слишком жестко. Тогда запретим ему заезжать туда где он был больше чем уже известное время проезда через город назад. Но это будет дооолго.