[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 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 = 1Output: 200Explanation: 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 = 0Output: 500Explanation: 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 个城市通过 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

  1 class Solution {      2         func findCheapestPrice(_ n: Int,_ flights: [[Int]],_ src: Int,_ dst: Int,_ K: Int) -> Int {  3         var grID = [[Int]](repeating: [Int](repeating: 0,count: n),count: n)  4         for flight in flights {  5             grID[flight[1]][flight[0]] = flight[2]  6         }  7         var k = K  8         var dsts = [(dst,0)],nextDst = [(Int,Int)]()  9         var ans = Int.max 10         while dsts.count > 0 && k >= 0 { 11             let (valIDDst,v) = dsts.removeFirst() 12             for i in grID[valIDDst].indices { 13                 if grID[valIDDst][i] != 0 { 14                     if i == src { ans = min(ans,grID[valIDDst][i] + v) } 15                     else { 16                         if ans >= grID[valIDDst][i] + v  { 17                             nextDst.append((i,grID[valIDDst][i] + v)) 18                         } 19                     } 20                 } 21             } 22             if dsts.count == 0 { 23                 dsts = nextDst 24                 nextDst.removeAll() 25                 k -= 1 26             } 27         } 28         return ans == Int.max ? -1 : ans 29     } 30      31     func mainBFS(_ n: Int,_ K: Int) -> Int { 32          33         var queue = Queue<City>() 34         queue.enqueue(src) 35          36         var visited = Set<City>() 37         var stops = 0 38         var cheapestPrice = 0 39          40         let graph = genGraph(flights) 41          42         while let fromCity = queue.dequeue() { 43              44             if fromCity == dst { 45                 return cheapestPrice 46             } 47              48             if stops == K { 49                 // check if we can make it to the destination  50                 // or return -1 since we will have exceeded max layovers 51                 var pricetoDst = -1 52                 if let nextCitIEs = graph[fromCity] { 53                     var i = 0 54                     var foundDst = false 55                     while i < nextCitIEs.count && !foundDst { 56                         if nextCitIEs[i] == dst { 57                             pricetoDst = cheapestPrice + price(flights,from: fromCity,to: nextCitIEs[i]) 58                             foundDst = true 59                         } 60                         i += 1 61                     } 62                 } 63                 return pricetoDst 64             } 65              66             // Look ahead and choose the next cheapest flight (Dijkstra‘s algorithm) 67             // important! This only works with positive edge values. 68             if let toCity = nextCheapestCity(from: fromCity,graph: graph,flights: flights) { 69  70                 // Don‘t revisit a city we have already traveled to 71                 if !visited.contains(toCity) { 72                    // visited.insert(toCity) 73  74                     // Cheapest prices so far 75                     cheapestPrice += price(flights,to: toCity) 76  77                     // Stops 78                     stops += 1 79  80                     // Enqueue next city 81                     queue.enqueue(toCity) 82                 } 83             } 84         } 85         print("returned here with cheapest price -> \(cheapestPrice)") 86         return -1 87     } 88      89     func mainDFS(_ n: Int,_ K: Int) -> Int { 90         var minPrice = Int.max 91         var curPrice = 0 92         var curLayovers = 0 93         var visited = Set<Int>() 94         var found = false 95         let graph = genGraph(flights) 96         visited.insert(src) 97         dfs(flights,dst: dst,k: K,vertex: src,curPrice: &curPrice,curLayovers: &curLayovers,visited: &visited,found: &found,minPrice: &minPrice) 98         return found ? minPrice : -1 99     }100     101     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) {102         if vertex == dst {103             found = true104             if curPrice < minPrice {105                 minPrice = curPrice106             }107             return108         }109         if curLayovers > k {110             return111         }112         113         if let destinations = graph[vertex] {114             destinations.forEach { neighbor in115             if !visited.contains(neighbor) {116                 var toprice = price(flights,from: vertex,to: neighbor)117                 curPrice += toprice118                 curLayovers += 1119                 dfs(flights,k: k,vertex: neighbor,minPrice: &minPrice)120                 visited.remove(neighbor)121                 curPrice -= toprice122                 curLayovers -= 1123             }124         }125         }126 127     }128     129     // Helpers130     131     typealias City = Int132     typealias Price = Int133         134     struct Queue<Element> {135         var storage = [Element]()136         mutating func enqueue(_ element: Element) {137             self.storage.append(element)138         }139         mutating func dequeue() -> Element? {140             guard self.storage.count > 0 else { return nil }141             return self.storage.removeFirst()142         }143     }144     145     func genGraph(_ flights: [[Int]]) -> [City: [City]] {146         var graph = [Int: [Int]]()147         flights.forEach { flight in 148             let from = flight[0]149             let to = flight[1]150             if var edges = graph[from] {151                 edges.append(to)152                 graph[from] = edges153             } else {154                 graph[from] = [to]155             }156         }157         return graph158     }159     160     func price(_ flights: [[Int]],from: Int,to: Int) -> Int {161         var i = 0162         while i < flights.count {163             let flight = flights[i]164             if from == flight[0],to == flight[1] {165                 return flight[2]166             }167             i += 1168         }169         return -1170     }171     172     // Note: This can be done when creating the graph instead for the BFS solution to improve performance173     func nextCheapestCity(from city: City,flights: [[Int]]) -> City? {174         var nextCity: City?175         var minPrice = Int.max176         if let toCitIEs = graph[city] {177             toCitIEs.forEach { toCity in178                 let pricetoCity = price(flights,from: city,to: toCity)179                 if pricetoCity < minPrice {180                     minPrice = pricetoCity181                     nextCity = toCity182                 }183             }184         }185         return nextCity186     }    187     // Helpers - end188 }

76ms

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

Runtime: 96 ms Memory Usage: 18.9 MB

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

96ms

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

100ms

 1 class Solution { 2     typealias Flight = (dst: Int,cost: Int) 3     func findCheapestPrice(_ n: Int,_ start: Int,_ end: Int,_ k: Int) -> Int { 4         guard flights.isEmpty == false else { 5             return 0 6         } 7         var dict: [Int: [Flight]] = [:] 8         for flight in flights { 9             dict[flight[0],default: []].append((flight[1],flight[2]))10         }11         12         var res = Int.max13         var queue: [Flight] = []14         queue.append((start,0))15         var stops = -116 17         while queue.isEmpty == false {18             let n = queue.count19             for _ in 0..<n {20                 let curFlight = queue.removeFirst()21                 let curStop = curFlight.dst22                 let cost = curFlight.cost23                 if curStop == end {24                     res = min(res,cost)25                     continue26                 }27                 for flight in (dict[curStop] ?? []) {28                     if cost + flight.cost > res {29                         continue30                     }31                     queue.append((flight.dst,cost + flight.cost))32                 }33             }34             stops += 135             if stops > k {36                 break37             }38         }39         return (res == Int.max) ? -1 : res40     }41 }

136ms

 1 class Solution { 2   func findCheapestPrice(_ n: Int,_ K: Int) -> Int { 3     var flightsMap = Dictionary<Int,Array<Flight>>() 4     var cache = Dictionary<CacheState,Int>()   5     for flight in flights { 6       let stFlight = Flight(destination: flight[1],cost: flight[2]) 7       if var array = flightsMap[flight[0]] { 8         array.append(stFlight) 9         flightsMap[flight[0]] = array10       } else {11         flightsMap[flight[0]] = [stFlight]12       }13     }14     let ans = dfs(K,src,dst,flightsMap,&cache)15     if ans == Int.max { return -1 }16     return ans17   }18   func dfs(19     _ remainingK: Int,20     _ currentNode: Int,21     _ dst: Int,22     _ flightsMap: Dictionary<Int,Array<Flight>>,23     _ cache: inout Dictionary<CacheState,Int>) -> Int {24     if currentNode == dst { return 0 }25     guard remainingK >= 0 else { return Int.max }26     var cacheState = CacheState(source: currentNode,K: remainingK)  27     if let val = cache[cacheState] { return val } 28     var ans = Int.max29     guard let array = flightsMap[currentNode] else { return Int.max }30     for flight in array {31       let curAns = dfs(remainingK - 1,flight.destination,&cache)32       if curAns != Int.max {33         ans = min(ans,curAns + flight.cost)34       }35     }36     cache[cacheState] = ans37     return ans38   }39 }40 41 struct Flight {42   let destination: Int43   let cost: Int44 }45 struct CacheState: Hashable {46   let source: Int47   let K: Int48 }

152ms

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

156ms

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

288ms

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

总结

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

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