# 787. Cheapest Flights Within K Stops

## ref 1 : Dijkstra::BFS

在 Dijkstra 這個演算法: BFS + priority queue(min heap).
這個概念下，加上 k 這個限制條件 (少於k及紀錄目前節點遇過最少的steps).

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        #Make graph
        adj_list = {i:[] for i in range(n)}
        for frm, to, price in flights:
            adj_list[frm].append((to, price))
        
        best_visited = [2**31]*n # Initialized to maximum
        
        prior_queue = [ (0, -1, src) ]  # weight, steps, node

        while prior_queue:
            cost, steps, node = heapq.heappop(prior_queue)
            
            if best_visited[node] <= steps:  # Have seen the node already, and the current steps are more than last time
                continue

            if steps > k:  # More than k stops, invalid
                continue

            if node==dst:  # reach the destination # as priority_queue is a minHeap so this cost is the most minimum cost.
                return cost
            
            best_visited[node] = steps # Update steps

            for neighb, weight in adj_list[node]:
                heapq.heappush(prior_queue, (cost + weight, steps + 1, neighb))

        return -1

## ref 2 : Bellman-Ford

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        # 限制為 k , 可執行次數為 k+1 ?
        # 在 k+1 round 中, 需找到src to dst的最少花費
        # 每一round, 走一層, 因此更新最少花費到達的邊, 不能以原有的圖來更新.

        price = [float("inf")]*n
        # starting point no need price
        price[src]=0

        for i in range(k+1): # 0~(k)

            tempPrice = price.copy()
            # update every edge if matching the condition 
            for f,t,p in flights:
                # if matching the condition
                if price[f] == float("inf"):
                    continue
                if price[f]+p < tempPrice[t]: # original or copy_of_original
                    tempPrice[t] = price[f]+p
            price = tempPrice.copy()

        return -1 if price[dst]==float("inf") else price[dst]