Не могу сказать, насколько это решение будет оптимальным по времени, не зная предполагаемого размера графа. Но есть решение через максимальный поток, котрое точно наилучшим способом пустит машины.
Раздуйте граф, сделав копии каждой вершины для каждого возможного времени. Т.е.если предполагается, что есть решение не длинее 1000 едениц веремни, то создаете граф с 1000*V вершинами, по одной для каждой вершины начального графа и возможного времени. Для каждого ребра входного графа u->v создайте ребро {u,t}->{u,t+1}. В этом графе есть много входных вершин (любое время, начальная вершина) и много конечных вершин (любое время). Но тут уже нет условия на непересечение машин в одно и то же время. Вместо этого пути машинок просто не могут пересекаться по вершинам вообще. Ведь каждая вершина символизирует вершину+время.
Теперь еще раз преобразуем граф - сделайте новую входную вершину и соедените ее со всеми входными вершинами в этом графе. Также сделайте новую конечную вершину и соедените ее со всеми конечными вершинами. Каждую оставшуюся вершину разделите на 2 - вход и выход. Все ребра ведущие в эту вершину пустите во вход, и так же поведите все ребра из начальной вершины из выхода. Соедените вход и выход ребром.
В этом графе пути уже должны не пересекаться по ребрам (ведь каждая вершина заменена ребром между двумя новыми вершинами) и все пути ведут из начала в конец. Чтобы разрешить машинам пересекаться в начальной и конечной вершине, начальные и конечные вершины графа не раздваивайте и сделайте пропускную способность ребер из начальной и в конечную вершины равными n. Все остальные пропускные способности равны 1.
Теперь пустите максимальный поток в этом шрафе, и он найдет вам сколько-то путей машин не пересекающихся по ребрам. Эти пути однозначно задают вам пути машин в изначальном графе - когда выпускать машину и по какому пути она идет.
Что бы найти оптимальный пути запустите бинарный поиск по ответу. Вот выбрали вы число 1000, создали искуственный граф со временем до 1000 для всех вершин. Запустили в нем максимальный поток. Если он нашел меньше n путей, то за 1000 едениц времени все n машин не пустить, пробуйте большее время. Если нашли хотя бы n путей, то можно взять любые n из них.
Изначальную верхнюю границу по времени можно взять n+V (V - путь в графе, и все машины идут по нему колонной одна за другой).
Возможно есть улучшение этого решения такое: Вместо бинарного поиска по ответу вы увеличиваете максимальное время на 1, добавляете новые вершины и ребра в граф и каждый раз ищете дополняющие пути (не отчищая уже найденый максимальный поток). Это рещение вроде будет побыстрее, но тут надо аккуратно понимать, что такое остаточная сеть.
Средний
