分类导航

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_91_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_91_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]，城市标签从 0 到 n - 1.
航班数量范围是 [0,n * (n - 1) / 2].
每个航班的格式 (src,pricE).
每个航班的价格范围是 [1,10000].
k 范围是 [0,n - 1].
航班没有重复，且不存在环路

68ms

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

76ms

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

Runtime: 96 ms

Memory Usage: 18.9 MB

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

96ms

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

100ms

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

136ms

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

152ms

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

156ms

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

288ms

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