Bug Report for cheapest-flight-path - Missing Test Case

[abhishek-agrl]

Bug Report for https://neetcode.io/problems/cheapest-flight-path

Please describe the bug below and include any steps to reproduce the bug or screenshots if possible.

This is not really a bug, but an important test case is missing. My approach passed all the available test cases but fails for the following testcase:

n=4
flights=[[0,1,10],[1,2,10],[2,3,10],[0,2,500]]
src=0
dst=3
k=2

My solution:

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        adj = defaultdict(list)
        for s, d, price in flights:
            adj[s].append((price, d))
        
        q = deque([(0, 0, src)]) # Stops, cost, curr_airport
        visited = set()

        min_cost = float("inf")
        while q:
            stops, cost, curr = q.popleft()
            if curr==dst:
                min_cost = min(min_cost, cost)
            if stops>k or curr in visited:
                continue
            
            visited.add(curr)
            for next_cost, next_dst in adj[curr]:
                q.append((stops+1, cost+next_cost, next_dst))
        
        return -1 if min_cost==float("inf") else min_cost

This is because in standard BFS, a visited set prevents infinite loops and redundant checks. But in this problem, edges have weights (prices). Because standard BFS explores level-by-level (by number of stops), the first time a node is reached, it is guaranteed to be the path with the fewest stops. However, it is not guaranteed to be the cheapest path. If I mark a node as visited just because I reached it quickly, I block the algorithm from exploring a path that might take more stops (but still ≤k) and is significantly cheaper.

Therefore, I suggest adding this test-case to prevent an incorrect solution such as the above pass. Thanks :)