Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-01-26 18:11:36
787. Cheapest Flights Within K Stops
给你一个边集合表示的有向图形,每个边表示一个航班且都有他的成本,求出从src到
dst的最小成本是多少,你最多只能搭k+1次飞机,若无法到达目的地则返回-1。
Example:
https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-3drawio.png
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.把航班的边转换成一个图形结构并保存他的成本。
2.从src的位置开始用BFS不断往外延伸,直到k用完或没点可以访问为止。
3.这边需要做剪枝不然会TLE,若当前点往下一个前往的点的成本比之前算过的成本高
的时候,就不把该点加入Queue,下个点就是终点的话也不用继续访问。
Java Code:
作者: DDFox (冒险者兼清洁工)   2023-01-26 18:15:00
大师
作者: SecondRun (雨夜琴声)   2023-01-26 18:17:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com