Как искать кратчайший путь с дополнительным состоянием (слоистый граф)?

Расширяем понятие «вершины»: состояние = (вершина, доп.информация). Для «k бесплатных рёбер» состояние (v, использовано_бонусов). Строим слоистый граф: k+1 копий исходного. В пределах слоя — обычные рёбра, переход между слоями — «использовать бонус». Запускаем Дейкстру/BFS по этому большому графу.

// dist[v][j] = кратчайший путь до v, потратив j бонусов
vector<vector<ll>> dist(n, vector<ll>(k+1, INF));
dist[s][0] = 0;
priority_queue<tuple<ll,int,int>, vector<tuple<ll,int,int>>, greater<>> pq;
pq.push({0, s, 0});
while (!pq.empty()) {
    auto [d, v, j] = pq.top(); pq.pop();
    if (d > dist[v][j]) continue;
    for (auto [u, w] : g[v]) {
        // обычное ребро
        if (d + w < dist[u][j]) { dist[u][j] = d + w; pq.push({dist[u][j], u, j}); }
        // потратить бонус (ребро бесплатно)
        if (j < k && d < dist[u][j+1]) { dist[u][j+1] = d; pq.push({dist[u][j+1], u, j+1}); }
    }
}

Сложность O((k+1)·E·log((k+1)·V)) по времени, O((k+1)·V) памяти — Дейкстра на графе, увеличенном в k+1 раз.