Как искать кратчайший путь, когда часть рёбер можно проходить только в определённое время (динамический граф)?

Ключевая идея — Дейкстра по времени прибытия как метрике. dist[v] = самый ранний момент, в который можно оказаться в v. При релаксации ребра (v -> u) смотрим, в какой момент это ребро доступно при условии, что мы пришли в v в момент dist[v], и считаем время прибытия в u. Поскольку «время прибытия» монотонно (раньше приехал — раньше уедешь дальше), жадность Дейкстры сохраняется.

// edge: {сосед u, момент отправления dep, длительность w}
vector<ll> dist(n, INF);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
dist[s] = 0; pq.push({0, s});
while (!pq.empty()) {
    auto [t, v] = pq.top(); pq.pop();
    if (t > dist[v]) continue;
    for (auto [u, dep, w] : g[v]) {
        if (dep < t) continue;           // рейс уже ушёл
        ll arr = dep + w;                // момент прибытия в u
        if (arr < dist[u]) { dist[u] = arr; pq.push({arr, u}); }
    }
}

Сложность O(E log V) — структурно та же Дейкстра, метрика — абсолютное время прибытия. Так решают задачи про расписания поездов/рейсов («time-dependent shortest path»).