787. Cheapest Flights Within K Stops
링크
https://leetcode.com/problems/cheapest-flights-within-k-stops/
문제 설명
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.
입력
출력
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
제한 조건
1 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= fromi, toi < n
fromi != toi
1 <= pricei <= 104
There will not be any multiple flights between two cities.
0 <= src, dst, k < n
src != dst
전체 코드
import heapq
class Solution:
def dijkstra(self,graph:dict,start:int,end:int,k:int)->int:
heap=[]
visited_set=set()
# (cost,node,visit_count)
visited_set.add((0,start,0))
#(node,cost,visit_count)
heapq.heappush(heap,(0,start,0))
while heap:
cost,node,visit_count=heapq.heappop(heap)
if node==end:
return cost
for adj_node,adj_cost in graph[node]:
new_state=(cost+adj_cost,adj_node,visit_count+1)
if visit_count+1<=k and new_state not in visited_set:
visited_set.add(new_state)
heapq.heappush(heap,new_state)
return -1
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph=dict()
for i in range(n):
graph[i]=[]
for u,v,cost in flights:
graph[u].append((v,cost))
return self.dijkstra(graph,src,dst,k+1)
해설
import heapq
class Solution:
def dijkstra(self,graph:dict,start:int,end:int,k:int)->int:
heap=[]
visited_set=set()
# (cost,node,visit_count)
visited_set.add((0,start,0))
#(node,cost,visit_count)
heapq.heappush(heap,(0,start,0))
while heap:
cost,node,visit_count=heapq.heappop(heap)
if node==end:
return cost
for adj_node,adj_cost in graph[node]:
new_state=(cost+adj_cost,adj_node,visit_count+1)
if visit_count+1<=k and new_state not in visited_set:
visited_set.add(new_state)
heapq.heappush(heap,new_state)
return -1
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph=dict()
for i in range(n):
graph[i]=[]
for u,v,cost in flights:
graph[u].append((v,cost))
return self.dijkstra(graph,src,dst,k+1)
방문했던 노드라도 방문 횟수에 따라 상태가 다르다. 따라서 힙에 담을 때 (비용,노드,방문 횟수) 튜플로 담아야 한다.
Author And Source
이 문제에 관하여(787. Cheapest Flights Within K Stops), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dasd412/787.-Cheapest-Flights-Within-K-Stops저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)