June Leetcode

2020/06/15

Cheapest Flights Within K Stops

week-2-june-8th-june-14th

Which language are used

• python3

How to solving

Graph를 만들고, BFS를 사용해서 Graphql를 순회하면서 min_price를 찾고, 리턴하는 방식으로 개발함.

Code

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        # dp = value, step
        n = len(flights)
        dp = collections.defaultdict(list)
        
        
        for u, v, w in flights:
            dp[u].append((v, w))
        
        queue = []
        queue = [(src, 0, 0)]
        min_price = 100000
        while len(queue):
            cur, queue = queue[0], queue[1:]
            cur_dst, cur_price, cur_step = cur
            if cur_dst == dst:
                min_price = min(min_price, cur_price)
                continue
            
            if cur_step<=K and cur_price<=min_price:
                for d, price in dp[cur[0]]:
                    queue.append((d, price + cur_price, cur_step + 1))
        
        return -1 if min_price == 100000 else min_price