There are n cities and a list of flights [from, to, price]. You want to fly from src to dst using at most k stops (so at most k + 1 edges). Return the cheapest price. If no route exists within the stop limit, return -1. Google interviews often include graph problems with constraints. This one tests modified BFS or Bellman-Ford thinking.
For flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1: the cheapest route is 0 → 1 → 2 for . The direct flight costs .
Plain Dijkstra won't work here. Why not? The stop constraint changes which paths are valid.
Constraints: , up to flights.