分类导航

Swift 发布时间：2022-03-31 发布网站：大佬教程 code.js-code.com

大佬教程收集整理的这篇文章主要介绍了[Swift]LeetCode787. K 站中转内最便宜的航班 | Cheapest Flights Within K Stops，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

概述

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w. Now given all the cities and flights, together with starTing city src and the desTination dst,

There are n cities connected by @H_189_19@m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and flights,together with starTing city src and the desTination dst,your task is to find the cheapest price from src to dst with up to k stops. If there is no such route,output -1.

Example 1:
Input: 
n = 3,edges = [[0,1,100],[1,2,[0,500]]
src = 0,dst = 2,k = 1
Output: 200
Explanation: 
The graph looks like this:

The cheapest price from city  to city  with at most 1 stop costs 200,as marked red in the picture.02

Example 2:
Input: 
n = 3,k = 0
Output: 500
Explanation: 
The graph looks like this:

The cheapest price from city  to city  with at most 0 stop costs 500,as marked blue in the picture.02

Note:

the number of nodes n will be in range [1,100],with nodes labeled from 0 to n - 1.
The size of flights will be in range [0,n * (n - 1) / 2].
The format of each flight will be (src, dst,pricE).
The price of each flight will be in the range [1,10000].
k is in the range of [0,n - 1].
There will not be any duplicated flights or self cycles.

有 n 个城市通过 @H_189_19@m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。如果没有这样的路线，则输出 -1。

示例 1:
输入: 
n = 3,k = 1
输出: 200
解释: 
城市航班图如下

从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2:
输入: 
n = 3,k = 0
输出: 500
解释: 
城市航班图如下

从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

提示：

n 范围是 [1,100]，城市@L_673_6@从 0 到 n - 1.
航班数量范围是 [0,n * (n - 1) / 2].
每个航班的格式 (src,pricE).
每个航班的价格范围是 [1,10000].
k 范围是 [0,n - 1].
航班没有重复，且不存在环路

68ms

  1@H_947_197@ class@H_947_197@ Solution {    
@H_947_197@  2@H_947_197@         func findCheapestPrice(_ n: Int,_ flights: [[Int]],_ src: Int,_ dst: Int,_ K: int) -> Int {
@H_947_197@  3@H_947_197@         var@H_947_197@ grid = [[Int]](repeaTing: [Int](repeaTing: 0@H_947_197@,count: n),count: n)
@H_947_197@  4@H_947_197@         for@H_947_197@ flight in@H_947_197@ flights {
@H_947_197@  5@H_947_197@             grid[flight[1@H_947_197@]][flight[0@H_947_197@]] = flight[2@H_947_197@]
@H_947_197@  6@H_947_197@         }
@H_947_197@  7@H_947_197@         var@H_947_197@ k = K
@H_947_197@  8@H_947_197@         var@H_947_197@ dsts = [(dst,0@H_947_197@)],nextDst = [(Int,int)]()
@H_947_197@  9@H_947_197@         var@H_947_197@ ans = Int.max
@H_947_197@ 10@H_947_197@         while@H_947_197@ dsts.count > 0@H_947_197@ && k >= 0@H_947_197@ {
@H_947_197@ 11@H_947_197@             let (validDst,v) = dsts.removeFirst()
@H_947_197@ 12@H_947_197@             for@H_947_197@ i in@H_947_197@ grid[validDst].inDices {
@H_947_197@ 13@H_947_197@                 if@H_947_197@ grid[validDst][i] != 0@H_947_197@ {
@H_947_197@ 14@H_947_197@                     if@H_947_197@ i == src { ans = min(ans,grid[validDst][i] + v) }
@H_947_197@ 15@H_947_197@                     else@H_947_197@ {
@H_947_197@ 16@H_947_197@                         if@H_947_197@ ans >= grid[validDst][i] + v  {
@H_947_197@ 17@H_947_197@                             nextDst.append((i,grid[validDst][i] + v))
@H_947_197@ 18@H_947_197@                         }
@H_947_197@ 19@H_947_197@                     }
@H_947_197@ 20@H_947_197@                 }
@H_947_197@ 21@H_947_197@             }
@H_947_197@ 22@H_947_197@             if@H_947_197@ dsts.count == 0@H_947_197@ {
@H_947_197@ 23@H_947_197@                 dsts = nextDst
@H_947_197@ 24@H_947_197@                 nextDst.removeAll()
@H_947_197@ 25@H_947_197@                 k -= 1@H_947_197@
 26@H_947_197@             }
@H_947_197@ 27@H_947_197@         }
@H_947_197@ 28@H_947_197@         return@H_947_197@ ans == Int.max ? -1@H_947_197@ : ans
@H_947_197@ 29@H_947_197@     }
@H_947_197@ 30@H_947_197@     
 31@H_947_197@     func mainBFS(_ n: Int,_ K: int) -> Int {
@H_947_197@ 32@H_947_197@         
 33@H_947_197@         var@H_947_197@ queue = Queue<City>()
@H_947_197@ 34@H_947_197@         queue.enqueue(srC)
@H_947_197@ 35@H_947_197@         
 36@H_947_197@         var@H_947_197@ visited = Set<City>()
@H_947_197@ 37@H_947_197@         var@H_947_197@ stops = 0@H_947_197@
 38@H_947_197@         var@H_947_197@ cheapestPrice = 0@H_947_197@
 39@H_947_197@         
 40@H_947_197@         let graph = genGraph(flights)
@H_947_197@ 41@H_947_197@         
 42@H_947_197@         while@H_947_197@ let fromCity = queue.dequeue() {
@H_947_197@ 43@H_947_197@             
 44@H_947_197@             if@H_947_197@ fromCity == dst {
@H_947_197@ 45@H_947_197@                 return@H_947_197@ cheapestPrice
@H_947_197@ 46@H_947_197@             }
@H_947_197@ 47@H_947_197@             
 48@H_947_197@             if@H_947_197@ stops == K {
@H_947_197@ 49@H_947_197@                 //@H_947_197@ check if we can make it to the desTination 
@H_947_197@ 50@H_947_197@                 //@H_947_197@ or return -1 since we will have exceeded max layovers@H_947_197@
 51@H_947_197@                 var@H_947_197@ priCEToDst = -1@H_947_197@
 52@H_947_197@                 if@H_947_197@ let nextCities = graph[fromCity] {
@H_947_197@ 53@H_947_197@                     var@H_947_197@ i = 0@H_947_197@
 54@H_947_197@                     var@H_947_197@ foundDst = false@H_947_197@
 55@H_947_197@                     while@H_947_197@ i < nextCities.count && !foundDst {
@H_947_197@ 56@H_947_197@                         if@H_947_197@ nextCities[i] == dst {
@H_947_197@ 57@H_947_197@                             priCEToDst = cheapestPrice + price(flights,from@H_947_197@: fromCity,to: nextCities[i])
@H_947_197@ 58@H_947_197@                             foundDst = true@H_947_197@
 59@H_947_197@                         }
@H_947_197@ 60@H_947_197@                         i += 1@H_947_197@
 61@H_947_197@                     }
@H_947_197@ 62@H_947_197@                 }
@H_947_197@ 63@H_947_197@                 return@H_947_197@ priCEToDst
@H_947_197@ 64@H_947_197@             }
@H_947_197@ 65@H_947_197@             
 66@H_947_197@             //@H_947_197@ Look ahead and choose the next cheapest flight (Dijkstra‘s algorithm)
@H_947_197@ 67@H_947_197@             //@H_947_197@ Important! This only works with positive edge values.@H_947_197@
 68@H_947_197@             if@H_947_197@ let toCity = nextCheapestCity(from@H_947_197@: fromCity,graph: graph,flights: flights) {
@H_947_197@ 69@H_947_197@ 
 70@H_947_197@                 //@H_947_197@ Don‘t revisit a city we have already traveled to@H_947_197@
 71@H_947_197@                 if@H_947_197@ !visited.contains(toCity) {
@H_947_197@ 72@H_947_197@                    //@H_947_197@ visited.insert(toCity)
@H_947_197@ 73@H_947_197@ 
 74@H_947_197@                     //@H_947_197@ Cheapest prices so far@H_947_197@
 75@H_947_197@                     cheapestPrice += price(flights,to: toCity)
 76@H_947_197@ 
 77@H_947_197@                     //@H_947_197@ Stops@H_947_197@
 78@H_947_197@                     stops += 1@H_947_197@
 79@H_947_197@ 
 80@H_947_197@                     //@H_947_197@ Enqueue next city@H_947_197@
 81@H_947_197@                     queue.enqueue(toCity)
@H_947_197@ 82@H_947_197@                 }
@H_947_197@ 83@H_947_197@             }
@H_947_197@ 84@H_947_197@         }
@H_947_197@ 85@H_947_197@         print(@H_770_616@"@H_947_197@@H_770_616@returned here with cheapest price -> \(cheapestPricE)@H_947_197@@H_770_616@"@H_947_197@)
@H_947_197@ 86@H_947_197@         return@H_947_197@ -1@H_947_197@
 87@H_947_197@     }
@H_947_197@ 88@H_947_197@     
 89@H_947_197@     func mainDFS(_ n: Int,_ K: int) -> Int {
@H_947_197@ 90@H_947_197@         var@H_947_197@ minPrice = Int.max
@H_947_197@ 91@H_947_197@         var@H_947_197@ curPrice = 0@H_947_197@
 92@H_947_197@         var@H_947_197@ curLayovers = 0@H_947_197@
 93@H_947_197@         var@H_947_197@ visited = Set<Int>()
@H_947_197@ 94@H_947_197@         var@H_947_197@ found = false@H_947_197@
 95@H_947_197@         let graph = genGraph(flights)
@H_947_197@ 96@H_947_197@         visited.insert(srC)
@H_947_197@ 97@H_947_197@         dfs(flights,dst: dst,k: K,vertex: src,curPrice: &curPrice,curLayovers: &curLayovers,visited: &visited,found: &found,minPrice: &@H_643_200@minPricE)
@H_947_197@ 98@H_947_197@         return@H_947_197@ found ? minPrice : -1@H_947_197@
 99@H_947_197@     }
@H_947_197@100@H_947_197@     
101@H_947_197@     func dfs(_ flights: [[Int]],dst: Int,k: Int,graph: [City: [City]],vertex: Int,curPrice: inout Int,curLayovers: inout Int,visited: inout Set<Int>,found: inout Bool,minPrice: inout int) {
@H_947_197@102@H_947_197@         if@H_947_197@ vertex == dst {
@H_947_197@103@H_947_197@             found = true@H_947_197@
104@H_947_197@             if@H_947_197@ curPrice < minPrice {
@H_947_197@105@H_947_197@                 minPrice = curPrice
@H_947_197@106@H_947_197@             }
@H_947_197@107@H_947_197@             return@H_947_197@
108@H_947_197@         }
@H_947_197@109@H_947_197@         if@H_947_197@ curLayovers > k {
@H_947_197@110@H_947_197@             return@H_947_197@
111@H_947_197@         }
@H_947_197@112@H_947_197@         
113@H_947_197@         if@H_947_197@ let desTinations = graph[vertex] {
@H_947_197@114@H_947_197@             desTinations.forEach { neighbor in@H_947_197@
115@H_947_197@             if@H_947_197@ !visited.contains(neighbor) {
@H_947_197@116@H_947_197@                 var@H_947_197@ toPrice = price(flights,from@H_947_197@: vertex,to: neighbor)
@H_947_197@117@H_947_197@                 curPrice += toPrice
@H_947_197@118@H_947_197@                 curLayovers += 1@H_947_197@
119@H_947_197@                 dfs(flights,k: k,vertex: neighbor,minPrice: &@H_643_200@minPricE)
@H_947_197@120@H_947_197@                 visited.remove(neighbor)
@H_947_197@121@H_947_197@                 curPrice -= toPrice
@H_947_197@122@H_947_197@                 curLayovers -= 1@H_947_197@
123@H_947_197@             }
@H_947_197@124@H_947_197@         }
@H_947_197@125@H_947_197@         }
@H_947_197@126@H_947_197@ 
127@H_947_197@     }
@H_947_197@128@H_947_197@     
129@H_947_197@     //@H_947_197@ Helpers@H_947_197@
130@H_947_197@     
131@H_947_197@     typealias City = Int
@H_947_197@132@H_947_197@     typealias Price = Int
@H_947_197@133@H_947_197@         
134@H_947_197@     struct@H_947_197@ Queue<Element> {
@H_947_197@135@H_947_197@         var@H_947_197@ storage = [Element]()
@H_947_197@136@H_947_197@         mutaTing func enqueue(_ element: Element) {
@H_947_197@137@H_947_197@             self.storage.append(element)
@H_947_197@138@H_947_197@         }
@H_947_197@139@H_947_197@         mutaTing func dequeue() -> Element? {
@H_947_197@140@H_947_197@             guard self.storage.count > 0@H_947_197@ else@H_947_197@ { return@H_947_197@ nil }
@H_947_197@141@H_947_197@             return@H_947_197@ self.storage.removeFirst()
@H_947_197@142@H_947_197@         }
@H_947_197@143@H_947_197@     }
@H_947_197@144@H_947_197@     
145@H_947_197@     func genGraph(_ flights: [[Int]]) -> [City: [City]] {
@H_947_197@146@H_947_197@         var@H_947_197@ graph = [Int: [Int]]()
@H_947_197@147@H_947_197@         flights.forEach { flight in@H_947_197@ 
148@H_947_197@             let from@H_947_197@ = flight[0@H_947_197@]
@H_947_197@149@H_947_197@             let to = flight[1@H_947_197@]
@H_947_197@150@H_947_197@             if@H_947_197@ var@H_947_197@ edges = graph[from@H_947_197@] {
@H_947_197@151@H_947_197@                 edges.append(to)
@H_947_197@152@H_947_197@                 graph[from@H_947_197@] = edges
@H_947_197@153@H_947_197@             } else@H_947_197@ {
@H_947_197@154@H_947_197@                 graph[from@H_947_197@] = [to]
@H_947_197@155@H_947_197@             }
@H_947_197@156@H_947_197@         }
@H_947_197@157@H_947_197@         return@H_947_197@ graph
@H_947_197@158@H_947_197@     }
@H_947_197@159@H_947_197@     
160@H_947_197@     func price(_ flights: [[Int]],from@H_947_197@: Int,to: int) -> Int {
@H_947_197@161@H_947_197@         var@H_947_197@ i = 0@H_947_197@
162@H_947_197@         while@H_947_197@ i < flights.count {
@H_947_197@163@H_947_197@             let flight = flights[i]
@H_947_197@164@H_947_197@             if@H_947_197@ from@H_947_197@ == flight[0@H_947_197@],to == flight[1@H_947_197@] {
@H_947_197@165@H_947_197@                 return@H_947_197@ flight[2@H_947_197@]
@H_947_197@166@H_947_197@             }
@H_947_197@167@H_947_197@             i += 1@H_947_197@
168@H_947_197@         }
@H_947_197@169@H_947_197@         return@H_947_197@ -1@H_947_197@
170@H_947_197@     }
@H_947_197@171@H_947_197@     
172@H_947_197@     //@H_947_197@ Note: This can be done when creaTing the graph instead for the BFS solution to improve perfoRMANce@H_947_197@
173@H_947_197@     func nextCheapestCity(from@H_947_197@ city: City,flights: [[Int]]) -> City? {
@H_947_197@174@H_947_197@         var@H_947_197@ nextCity: City?
175@H_947_197@         var@H_947_197@ minPrice = Int.max
@H_947_197@176@H_947_197@         if@H_947_197@ let toCities = graph[city] {
@H_947_197@177@H_947_197@             toCities.forEach { toCity in@H_947_197@
178@H_947_197@                 let priCEToCity = price(flights,from@H_947_197@: city,to: toCity)
@H_947_197@179@H_947_197@                 if@H_947_197@ priCEToCity < minPrice {
@H_947_197@180@H_947_197@                     minPrice = priCEToCity
@H_947_197@181@H_947_197@                     nextCity = toCity
@H_947_197@182@H_947_197@                 }
@H_947_197@183@H_947_197@             }
@H_947_197@184@H_947_197@         }
@H_947_197@185@H_947_197@         return@H_947_197@ nextCity
@H_947_197@186@H_947_197@     }    
@H_947_197@187@H_947_197@     //@H_947_197@ Helpers - end@H_947_197@
188@H_947_197@ }

76ms

 1@H_947_197@ class@H_947_197@ Solution {
@H_947_197@ 2@H_947_197@     func findCheapestPrice(_ n: Int,_ K: int) -> Int {
@H_947_197@ 3@H_947_197@         var@H_947_197@ grid = [[Int]](repeaTing: [Int](repeaTing: 0@H_947_197@,count: n)
@H_947_197@ 4@H_947_197@         for@H_947_197@ flight in@H_947_197@ flights {
@H_947_197@ 5@H_947_197@             grid[flight[1@H_947_197@]][flight[0@H_947_197@]] = flight[2@H_947_197@]
@H_947_197@ 6@H_947_197@         }
@H_947_197@ 7@H_947_197@         var@H_947_197@ k = K
@H_947_197@ 8@H_947_197@         var@H_947_197@ dsts = [(dst,int)]()
 9@H_947_197@         var@H_947_197@ ans = Int.max
@H_947_197@10@H_947_197@         while@H_947_197@ dsts.count > 0@H_947_197@ && k >= 0@H_947_197@ {
@H_947_197@11@H_947_197@             let (validDst,v) = dsts.removeFirst()
@H_947_197@12@H_947_197@             for@H_947_197@ i in@H_947_197@ grid[validDst].inDices {
@H_947_197@13@H_947_197@                 if@H_947_197@ grid[validDst][i] != 0@H_947_197@ {
@H_947_197@14@H_947_197@                     if@H_947_197@ i == src { ans = min(ans,grid[validDst][i] + v) }
@H_947_197@15@H_947_197@                     else@H_947_197@ {
@H_947_197@16@H_947_197@                         if@H_947_197@ ans >= grid[validDst][i] + v  {
@H_947_197@17@H_947_197@                             nextDst.append((i,grid[validDst][i] + v))
@H_947_197@18@H_947_197@                         }
@H_947_197@19@H_947_197@                     }
@H_947_197@20@H_947_197@                 }
@H_947_197@21@H_947_197@             }
@H_947_197@22@H_947_197@ 
23@H_947_197@             if@H_947_197@ dsts.count == 0@H_947_197@ {
@H_947_197@24@H_947_197@                 dsts = nextDst
@H_947_197@25@H_947_197@                 nextDst.removeAll()
@H_947_197@26@H_947_197@                 k -= 1@H_947_197@
27@H_947_197@             }
@H_947_197@28@H_947_197@         }
@H_947_197@29@H_947_197@         return@H_947_197@ ans == Int.max ? -1@H_947_197@ : ans
@H_947_197@30@H_947_197@     }
@H_947_197@31@H_947_197@ }

Runtime: 96 ms

Memory Usage: 18.9 MB

 1@H_947_197@ class@H_947_197@ Solution {
@H_947_197@ 2@H_947_197@     func findCheapestPrice(_ n: Int,_ K: int) -> Int {
@H_947_197@ 3@H_947_197@         var@H_947_197@ dp:[Double] = [Double](repeaTing:1e9,count:n)
@H_947_197@ 4@H_947_197@         dp[src] = 0@H_947_197@
 5@H_947_197@         for@H_947_197@ i in@H_947_197@ 0@H_947_197@...K
@H_947_197@ 6@H_947_197@         {
@H_947_197@ 7@H_947_197@             var@H_947_197@ t:[Double] = dp
@H_947_197@ 8@H_947_197@             for@H_947_197@ x in@H_947_197@ flights
@H_947_197@ 9@H_947_197@             {
@H_947_197@10@H_947_197@                 t[x[1@H_947_197@]] = min(t[x[1@H_947_197@]],dp[x[0@H_947_197@]] + Double(x[2@H_947_197@]))
@H_947_197@11@H_947_197@             }
@H_947_197@12@H_947_197@             dp = t
@H_947_197@13@H_947_197@         }
@H_947_197@14@H_947_197@         return@H_947_197@ (dp[dst] >= 1e9) ? -1@H_947_197@ : Int(dp[dst])
@H_947_197@15@H_947_197@     }
@H_947_197@16@H_947_197@ }

96ms

 1@H_947_197@ class@H_947_197@ Solution {
@H_947_197@ 2@H_947_197@     func findCheapestPrice(_ n: Int,_ K: int) -> Int {
@H_947_197@ 3@H_947_197@         
 4@H_947_197@         
 5@H_947_197@         let maxValue = 2147483647@H_947_197@
 6@H_947_197@         
 7@H_947_197@         var@H_947_197@ ShortestPath = [Int](repeaTing: maxValue,count: n)
@H_947_197@ 8@H_947_197@         ShortestPath[src] = 0@H_947_197@
 9@H_947_197@         
10@H_947_197@         for@H_947_197@ _ in@H_947_197@ 0@H_947_197@...K{
@H_947_197@11@H_947_197@             var@H_947_197@ currentShortestPath = ShortestPath
@H_947_197@12@H_947_197@             
13@H_947_197@             for@H_947_197@ i in@H_947_197@ 0@H_947_197@..<flights.count{
@H_947_197@14@H_947_197@                 let flight = flights[i]
@H_947_197@15@H_947_197@                 let originCity      = flight[0@H_947_197@]
@H_947_197@16@H_947_197@                 let desTinationCity = flight[1@H_947_197@]
@H_947_197@17@H_947_197@                 let fLightcost      = flight[2@H_947_197@]
@H_947_197@18@H_947_197@                 
19@H_947_197@           
20@H_947_197@                 
21@H_947_197@                 currentShortestPath[desTinationCity] = min(currentShortestPath[desTinationCity],@H_947_197@22@H_947_197@                                                           ShortestPath[originCity] + fLightcost)
@H_947_197@23@H_947_197@                 
24@H_947_197@             } 
@H_947_197@25@H_947_197@             ShortestPath = currentShortestPath
@H_947_197@26@H_947_197@         }
@H_947_197@27@H_947_197@         
28@H_947_197@         
29@H_947_197@         if@H_947_197@ ShortestPath[dst] == maxValue{
@H_947_197@30@H_947_197@             return@H_947_197@ -1@H_947_197@
31@H_947_197@         }else@H_947_197@{
@H_947_197@32@H_947_197@             return@H_947_197@ ShortestPath[dst]
@H_947_197@33@H_947_197@         }
@H_947_197@34@H_947_197@     }
@H_947_197@35@H_947_197@ }

100ms

 1@H_947_197@ class@H_947_197@ Solution {
@H_947_197@ 2@H_947_197@     typealias Flight = (dst: Int,cost: int)
@H_947_197@ 3@H_947_197@     func findCheapestPrice(_ n: Int,_ start: Int,_ end: Int,_ k: int) -> Int {
@H_947_197@ 4@H_947_197@         guard flights.isEmpty == false@H_947_197@ else@H_947_197@ {
@H_947_197@ 5@H_947_197@             return@H_947_197@ 0@H_947_197@
 6@H_947_197@         }
@H_947_197@ 7@H_947_197@         var@H_947_197@ Dict: [Int: [Flight]] = [:]
@H_947_197@ 8@H_947_197@         for@H_947_197@ flight in@H_947_197@ flights {
@H_947_197@ 9@H_947_197@             Dict[flight[0@H_947_197@],default@H_947_197@: []].append((flight[1@H_947_197@],flight[2@H_947_197@]))
@H_947_197@10@H_947_197@         }
@H_947_197@11@H_947_197@         
12@H_947_197@         var@H_947_197@ res = Int.max
@H_947_197@13@H_947_197@         var@H_947_197@ queue: [Flight] = []
@H_947_197@14@H_947_197@         queue.append((start,0@H_947_197@))
@H_947_197@15@H_947_197@         var@H_947_197@ stops = -1@H_947_197@
16@H_947_197@ 
17@H_947_197@         while@H_947_197@ queue.isEmpty == false@H_947_197@ {
@H_947_197@18@H_947_197@             let n = queue.count
@H_947_197@19@H_947_197@             for@H_947_197@ _ in@H_947_197@ 0@H_947_197@..<n {
@H_947_197@20@H_947_197@                 let curFlight = queue.removeFirst()
@H_947_197@21@H_947_197@                 let curstop = curFlight.dst
@H_947_197@22@H_947_197@                 let cost = curFlight.cost
@H_947_197@23@H_947_197@                 if@H_947_197@ curstop == end {
@H_947_197@24@H_947_197@                     res = min(res,cost)
@H_947_197@25@H_947_197@                     conTinue@H_947_197@
26@H_947_197@                 }
@H_947_197@27@H_947_197@                 for@H_947_197@ flight in@H_947_197@ (Dict[curstop] ?? []) {
@H_947_197@28@H_947_197@                     if@H_947_197@ cost + flight.cost > res {
@H_947_197@29@H_947_197@                         conTinue@H_947_197@
30@H_947_197@                     }
@H_947_197@31@H_947_197@                     queue.append((flight.dst,cost + flight.cost))
@H_947_197@32@H_947_197@                 }
@H_947_197@33@H_947_197@             }
@H_947_197@34@H_947_197@             stops += 1@H_947_197@
35@H_947_197@             if@H_947_197@ stops > k {
@H_947_197@36@H_947_197@                 break@H_947_197@
37@H_947_197@             }
@H_947_197@38@H_947_197@         }
@H_947_197@39@H_947_197@         return@H_947_197@ (res == Int.maX) ? -1@H_947_197@ : res
@H_947_197@40@H_947_197@     }
@H_947_197@41@H_947_197@ }

136ms

 1@H_947_197@ class@H_947_197@ Solution {
@H_947_197@ 2@H_947_197@   func findCheapestPrice(_ n: Int,_ K: int) -> Int {
@H_947_197@ 3@H_947_197@     var@H_947_197@ flightsmap = Dictionary<Int,Array<Flight>>()
@H_947_197@ 4@H_947_197@     var@H_947_197@ cache = Dictionary<CacheState,Int>()  
@H_947_197@ 5@H_947_197@     for@H_947_197@ flight in@H_947_197@ flights {
@H_947_197@ 6@H_947_197@       let stFlight = Flight(desTination: flight[1@H_947_197@],cost: flight[2@H_947_197@])
@H_947_197@ 7@H_947_197@       if@H_947_197@ var@H_947_197@ array = flightsmap[flight[0@H_947_197@]] {
@H_947_197@ 8@H_947_197@         array.append(stFlight)
@H_947_197@ 9@H_947_197@         flightsmap[flight[0@H_947_197@]] = array
@H_947_197@10@H_947_197@       } else@H_947_197@ {
@H_947_197@11@H_947_197@         flightsmap[flight[0@H_947_197@]] = [stFlight]
@H_947_197@12@H_947_197@       }
@H_947_197@13@H_947_197@     }
@H_947_197@14@H_947_197@     let ans = dfs(K,src,dst,flightsmap,&cachE)
@H_947_197@15@H_947_197@     if@H_947_197@ ans == Int.max { return@H_947_197@ -1@H_947_197@ }
@H_947_197@16@H_947_197@     return@H_947_197@ ans
@H_947_197@17@H_947_197@   }
@H_947_197@18@H_947_197@   func dfs(
@H_947_197@19@H_947_197@     _ remainingK: Int,@H_947_197@20@H_947_197@     _ currentNode: Int,@H_947_197@21@H_947_197@     _ dst: Int,@H_947_197@22@H_947_197@     _ flightsmap: Dictionary<Int,Array<Flight>>,@H_947_197@23@H_947_197@     _ cache: inout Dictionary<CacheState,Int>) -> Int {
@H_947_197@24@H_947_197@     if@H_947_197@ currentNode == dst { return@H_947_197@ 0@H_947_197@ }
@H_947_197@25@H_947_197@     guard remainingK >= 0@H_947_197@ else@H_947_197@ { return@H_947_197@ Int.max }
@H_947_197@26@H_947_197@     var@H_947_197@ cacheState = CacheState(source: currentNode,K: remainingK)  
@H_947_197@27@H_947_197@     if@H_947_197@ let val = cache[cacheState] { return@H_947_197@ val } 
@H_947_197@28@H_947_197@     var@H_947_197@ ans = Int.max
@H_947_197@29@H_947_197@     guard let array = flightsmap[currentNode] else@H_947_197@ { return@H_947_197@ Int.max }
@H_947_197@30@H_947_197@     for@H_947_197@ flight in@H_947_197@ array {
@H_947_197@31@H_947_197@       let curAns = dfs(remainingK - 1@H_947_197@,flight.desTination,&cachE)
@H_947_197@32@H_947_197@       if@H_947_197@ curAns != Int.max {
@H_947_197@33@H_947_197@         ans = min(ans,curAns + flight.cost)
@H_947_197@34@H_947_197@       }
@H_947_197@35@H_947_197@     }
@H_947_197@36@H_947_197@     cache[cacheState] = ans
@H_947_197@37@H_947_197@     return@H_947_197@ ans
@H_947_197@38@H_947_197@   }
@H_947_197@39@H_947_197@ }
@H_947_197@40@H_947_197@ 
41@H_947_197@ struct@H_947_197@ Flight {
@H_947_197@42@H_947_197@   let desTination: Int
@H_947_197@43@H_947_197@   let cost: Int
@H_947_197@44@H_947_197@ }
@H_947_197@45@H_947_197@ struct@H_947_197@ CacheState: Hashable {
@H_947_197@46@H_947_197@   let source: Int
@H_947_197@47@H_947_197@   let K: Int
@H_947_197@48@H_947_197@ }

152ms

 1@H_947_197@ class@H_947_197@ Solution {
@H_947_197@ 2@H_947_197@     func findCheapestPrice(_ n: Int,_ K: int) -> Int {
@H_947_197@ 3@H_947_197@         let Dict =  flights.reduce(into: [Int: [(Int,int)]]()) {
@H_947_197@ 4@H_947_197@             $0@H_947_197@[$1@H_947_197@[0@H_947_197@],default@H_947_197@:[]].append(($1@H_947_197@[1@H_947_197@],$1@H_947_197@[2@H_947_197@]))
@H_947_197@ 5@H_947_197@         }
@H_947_197@ 6@H_947_197@         var@H_947_197@ cache: [[Int?]] = Array(repeaTing: Array(repeaTing: nil,count: K+1@H_947_197@),count: n)
@H_947_197@ 7@H_947_197@         let c = dfs(Dict,K,&cachE)
@H_947_197@ 8@H_947_197@         return@H_947_197@ c 
@H_947_197@ 9@H_947_197@     }
@H_947_197@10@H_947_197@     
11@H_947_197@     func dfs(_ flights: [Int: [(Int,int)]],_ K: Int,_ cache: inout [[Int?]]) -> Int {
@H_947_197@12@H_947_197@         guard src != dst else@H_947_197@ { return@H_947_197@ 0@H_947_197@ }
@H_947_197@13@H_947_197@         guard K >= 0@H_947_197@ else@H_947_197@ { return@H_947_197@ -1@H_947_197@ }
@H_947_197@14@H_947_197@         var@H_947_197@ m : Int?
15@H_947_197@         if@H_947_197@ let dests = flights[src] { 
@H_947_197@16@H_947_197@             for@H_947_197@ f in@H_947_197@ dests {
@H_947_197@17@H_947_197@                 let c = cache[f.0@H_947_197@][K] ?? dfs(flights,f.0@H_947_197@,K-1@H_947_197@,&cachE)
@H_947_197@18@H_947_197@                 if@H_947_197@ c != -1@H_947_197@ {
@H_947_197@19@H_947_197@                    cache[f.0@H_947_197@][K] = c
@H_947_197@20@H_947_197@                    m = min(m ?? Int.max,c+f.1@H_947_197@) 
@H_947_197@21@H_947_197@                 }  else@H_947_197@ {
@H_947_197@22@H_947_197@                     cache[f.0@H_947_197@][K] = -1@H_947_197@
23@H_947_197@                 }
@H_947_197@24@H_947_197@             }
@H_947_197@25@H_947_197@         }
@H_947_197@26@H_947_197@         return@H_947_197@ m ?? -1@H_947_197@
27@H_947_197@     }
@H_947_197@28@H_947_197@ }

156ms

 1@H_947_197@ class@H_947_197@ Solution {
@H_947_197@ 2@H_947_197@     var@H_947_197@ res = Int.max
@H_947_197@ 3@H_947_197@     func findCheapestPrice(_ n: Int,_ K: int) -> Int {
@H_947_197@ 4@H_947_197@         var@H_947_197@ graph: [Int: [(Int,int)]] = [:]
@H_947_197@ 5@H_947_197@ 
 6@H_947_197@         for@H_947_197@ f in@H_947_197@ flights {
@H_947_197@ 7@H_947_197@             let start = f[0@H_947_197@],end = f[1@H_947_197@],price = f[2@H_947_197@]
@H_947_197@ 8@H_947_197@             graph[start,default@H_947_197@: []].append((end,pricE))
@H_947_197@ 9@H_947_197@         }
@H_947_197@10@H_947_197@         var@H_947_197@ visited = Set<Int>()
@H_947_197@11@H_947_197@         var@H_947_197@ dp: [Int: Int] = [:]
@H_947_197@12@H_947_197@         dfs(graph,&dp,0@H_947_197@,&visited,K)
@H_947_197@13@H_947_197@         return@H_947_197@ res == Int.max ? -1@H_947_197@ : res
@H_947_197@14@H_947_197@     }
@H_947_197@15@H_947_197@ 
16@H_947_197@     private@H_947_197@ func dfs(_ graph: [Int: [(Int,_ dp: inout [Int: Int],_ cost: Int,_ visited: inout Set<Int>,_ remaining: int) {
@H_947_197@17@H_947_197@         if@H_947_197@ start == end {
@H_947_197@18@H_947_197@             res = min(cost,res)
@H_947_197@19@H_947_197@         }
@H_947_197@20@H_947_197@ 
21@H_947_197@         if@H_947_197@ remaining < 0@H_947_197@ || cost >= res {
@H_947_197@22@H_947_197@             return@H_947_197@
23@H_947_197@         }
@H_947_197@24@H_947_197@ 
25@H_947_197@         if@H_947_197@ let loWest = dp[start] {
@H_947_197@26@H_947_197@             if@H_947_197@ loWest < cost {
@H_947_197@27@H_947_197@                 return@H_947_197@
28@H_947_197@             }
@H_947_197@29@H_947_197@         }
@H_947_197@30@H_947_197@         dp[start] = cost
@H_947_197@31@H_947_197@ 
32@H_947_197@         var@H_947_197@ forwardcost = Int.max
@H_947_197@33@H_947_197@         if@H_947_197@ let outgoing = graph[start] {
@H_947_197@34@H_947_197@             for@H_947_197@ edge in@H_947_197@ outgoing {
@H_947_197@35@H_947_197@                 dfs(graph,cost + edge.1@H_947_197@,&visited,edge.0@H_947_197@,end,remaining - 1@H_947_197@)
@H_947_197@36@H_947_197@             }
@H_947_197@37@H_947_197@         }
@H_947_197@38@H_947_197@     }
@H_947_197@39@H_947_197@ }

288ms

 1@H_947_197@ class@H_947_197@ Solution {
@H_947_197@ 2@H_947_197@     var@H_947_197@ dp = [[Int]]()
@H_947_197@ 3@H_947_197@     var@H_947_197@ graph = [[Int]]()
@H_947_197@ 4@H_947_197@     
 5@H_947_197@     func find(_ flights: [[Int]],_ k: Int,_ n: int) -> Int {
@H_947_197@ 6@H_947_197@         if@H_947_197@ src == dst {
@H_947_197@ 7@H_947_197@             dp[src][k] = 0@H_947_197@
 8@H_947_197@             return@H_947_197@ dp[src][k]
@H_947_197@ 9@H_947_197@         }
@H_947_197@10@H_947_197@         if@H_947_197@ k == 0@H_947_197@ {
@H_947_197@11@H_947_197@             dp[dst][k] = graph[dst][src]
@H_947_197@12@H_947_197@             return@H_947_197@ dp[dst][k]
@H_947_197@13@H_947_197@         }
@H_947_197@14@H_947_197@         if@H_947_197@ dp[dst][k] != Int.max {
@H_947_197@15@H_947_197@             return@H_947_197@ dp[dst][k]
@H_947_197@16@H_947_197@         }
@H_947_197@17@H_947_197@         
18@H_947_197@         for@H_947_197@ i in@H_947_197@ 0@H_947_197@..<n {
@H_947_197@19@H_947_197@             if@H_947_197@ graph[dst][i] != Int.max && find(flights,i,k-1@H_947_197@,n) != Int.max {
@H_947_197@20@H_947_197@                 dp[dst][k] = min(dp[dst][k],graph[dst][i] + find(flights,k-1@H_947_197@,n))
@H_947_197@21@H_947_197@             }
@H_947_197@22@H_947_197@         }
@H_947_197@23@H_947_197@         return@H_947_197@ dp[dst][k]
@H_947_197@24@H_947_197@     }
@H_947_197@25@H_947_197@     
26@H_947_197@     func findCheapestPrice(_ n: Int,_ K: int) -> Int {
@H_947_197@27@H_947_197@         dp = [[Int]](repeaTing: [Int](repeaTing: Int.max,count: n)
28@H_947_197@         graph = [[Int]](repeaTing: [Int](repeaTing: Int.max,count: n)
@H_947_197@29@H_947_197@         for@H_947_197@ f in@H_947_197@ flights {
@H_947_197@30@H_947_197@             graph[f[1@H_947_197@]][f[0@H_947_197@]] = f[2@H_947_197@]
@H_947_197@31@H_947_197@         }
@H_947_197@32@H_947_197@         return@H_947_197@ find(flights,n) == Int.max ? -1@H_947_197@ : dp[dst][K]
@H_947_197@33@H_947_197@     }
@H_947_197@34@H_947_197@ }

大佬总结

以上是大佬教程为你收集整理的[Swift]LeetCode787. K 站中转内最便宜的航班 | Cheapest Flights Within K Stops全部内容，希望文章能够帮你解决[Swift]LeetCode787. K 站中转内最便宜的航班 | Cheapest Flights Within K Stops所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。

标签：787 cheapest flights k leetcode leetcode787 stops swift 中转内最便宜站航班

上一篇: [Swift]LeetCode798. 得分最高的... 下一篇:[Swift]LeetCode789. 逃脱阻碍者...

猜你在找的Swift相关文章

通知 – 如何实现多个本地通知而不是swift 3的单个通知 2019-10-14
Swift 【基于 Swift 面向协议编程】 2022-03-31
swift – 获取字符串的长度 2022-03-31
Swift中Selector的用法 2022-03-31
swift – 强制展开的目的 2019-10-14
Swift协议扩展实现具有共享关联类型的另一协议 2022-04-30
在Swift中展平多个数组的所有值 2019-10-14
如何检查核心数据是否为空 2019-10-14
错误：类型’String’的值在Swift中没有成员’Generator’ 2019-10-14
如何在swift中使用if语句检查枚举？ 2019-10-14