Today I learned
2022/02/07
회고록
항해 99, 알고리즘 4주차(항해 5주차)
교재 : 파이썬 알고리즘 인터뷰 / 이것이 코딩테스트다(동빈좌)
최단경로
이론 정리 포스팅 글(내 벨로그)
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
Example 1:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The graph is shown.
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
https://leetcode.com/problems/cheapest-flights-within-k-stops/
from collections import defaultdict
import heapq
from typing import List
INF = float('inf')
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
adj = defaultdict(dict)
for f, t, p in flights:
adj[f][t] = p
print(adj)
stop = [INF] * n
heap = [(0, 0, src)]
while heap:
current_price, current_stop, current_node = heapq.heappop(heap)
if current_node == dst:
return current_price
if current_stop == k + 1 or current_stop >= stop[current_node]:
continue
stop[current_node] = current_stop
for c, p in adj[current_node].items():
heapq.heappush(heap, (current_price + p, current_stop + 1, c))
return -1
다익스트라 알고리즘 익히기