LeetCode 787 Cheapest Flights Within K Stops - Algorithm

Each heap entry stores three values: (cost, city, stops_remaining). You pop the cheapest cost first, as always. When you pop state (cost, u, k), you check neighbors of city u. For each neighbor v with edge cost w, you push (cost + w, v, k - 1) onto the heap, but only if k > 0.

If k = 0, you've used all your stops. You can't explore further from this state. You might still find the destination from a different path that used fewer stops.

Each state is a $(city, stops)$ pair, so the state space grows to $V \times k$. This runs in $O(E \cdot k \cdot \log(V \cdot k))$ time and uses $O(V \cdot k)$ space.