[Swift]LeetCode787.K站中转内最便宜的航班|CheapestFlightsWithinKStops

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10545382.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
Explanation: 
The graph looks like this:

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

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

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

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, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释: 
城市航班图如下

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

示例 2:
输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释: 
城市航班图如下

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

提示：

n 范围是 [1, 100]，城市标签从 0 到 n - 1.
航班数量范围是 [0, n * (n - 1) / 2].
每个航班的格式 (src, dst, 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, _ flights: [[Int]], _ src: Int, _ dst: 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, from: fromCity, 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, _ flights: [[Int]], _ src: Int, _ dst: 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, graph: graph, 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 = true
104             if curPrice < minPrice {
105                 minPrice = curPrice
106             }
107             return
108         }
109         if curLayovers > k {
110             return
111         }
112         
113         if let destinations = graph[vertex] {
114             destinations.forEach { neighbor in
115             if !visited.contains(neighbor) {
116                 var toPrice = price(flights, from: vertex, to: neighbor)
117                 curPrice += toPrice
118                 curLayovers += 1
119                 dfs(flights, dst: dst, k: k, graph: graph, vertex: neighbor, curPrice: &curPrice, curLayovers: &curLayovers, visited: &visited, found: &found, minPrice: &minPrice)
120                 visited.remove(neighbor)
121                 curPrice -= toPrice
122                 curLayovers -= 1
123             }
124         }
125         }
126 
127     }
128     
129     // Helpers
130     
131     typealias City = Int
132     typealias Price = Int
133         
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] = edges
153             } else {
154                 graph[from] = [to]
155             }
156         }
157         return graph
158     }
159     
160     func price(_ flights: [[Int]], from: Int, to: Int) -> Int {
161         var i = 0
162         while i < flights.count {
163             let flight = flights[i]
164             if from == flight[0], to == flight[1] {
165                 return flight[2]
166             }
167             i += 1
168         }
169         return -1
170     }
171     
172     // Note: This can be done when creating the graph instead for the BFS solution to improve performance
173     func nextCheapestCity(from city: City, graph: [City: [City]], flights: [[Int]]) -> City? {
174         var nextCity: City?
175         var minPrice = Int.max
176         if let toCities = graph[city] {
177             toCities.forEach { toCity in
178                 let priceToCity = price(flights, from: city, to: toCity)
179                 if priceToCity < minPrice {
180                     minPrice = priceToCity
181                     nextCity = toCity
182                 }
183             }
184         }
185         return nextCity
186     }    
187     // Helpers - end
188 }

76ms

 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 
23             if dsts.count == 0 {
24                 dsts = nextDst
25                 nextDst.removeAll()
26                 k -= 1
27             }
28         }
29         return ans == Int.max ? -1 : ans
30     }
31 }

Runtime: 96 ms

Memory Usage: 18.9 MB

 1 class Solution {
 2     func findCheapestPrice(_ n: Int, _ flights: [[Int]], _ src: Int, _ dst: 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 = t
13         }
14         return (dp[dst] >= 1e9) ? -1 : Int(dp[dst])
15     }
16 }

96ms

 1 class Solution {
 2     func findCheapestPrice(_ n: Int, _ flights: [[Int]], _ src: Int, _ dst: 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 = ShortestPath
12             
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 = currentShortestPath
26         }
27         
28         
29         if ShortestPath[dst] == maxValue{
30             return -1
31         }else{
32             return ShortestPath[dst]
33         }
34     }
35 }

100ms

 1 class Solution {
 2     typealias Flight = (dst: Int, cost: Int)
 3     func findCheapestPrice(_ n: Int, _ flights: [[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.max
13         var queue: [Flight] = []
14         queue.append((start, 0))
15         var stops = -1
16 
17         while queue.isEmpty == false {
18             let n = queue.count
19             for _ in 0..<n {
20                 let curFlight = queue.removeFirst()
21                 let curStop = curFlight.dst
22                 let cost = curFlight.cost
23                 if curStop == end {
24                     res = min(res, cost)
25                     continue
26                 }
27                 for flight in (dict[curStop] ?? []) {
28                     if cost + flight.cost > res {
29                         continue
30                     }
31                     queue.append((flight.dst, cost + flight.cost))
32                 }
33             }
34             stops += 1
35             if stops > k {
36                 break
37             }
38         }
39         return (res == Int.max) ? -1 : res
40     }
41 }

136ms

 1 class Solution {
 2   func findCheapestPrice(_ n: Int, _ flights: [[Int]], _ src: Int, _ dst: 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]] = array
10       } 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 ans
17   }
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.max
29     guard let array = flightsMap[currentNode] else { return Int.max }
30     for flight in array {
31       let curAns = dfs(remainingK - 1, flight.destination, dst, flightsMap, &cache)
32       if curAns != Int.max {
33         ans = min(ans, curAns + flight.cost)
34       }
35     }
36     cache[cacheState] = ans
37     return ans
38   }
39 }
40 
41 struct Flight {
42   let destination: Int
43   let cost: Int
44 }
45 struct CacheState: Hashable {
46   let source: Int
47   let K: Int
48 }

152ms

 1 class Solution {
 2     func findCheapestPrice(_ n: Int, _ flights: [[Int]], _ src: Int, _ dst: 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, src, dst, K, &cache)
 8         return c 
 9     }
10     
11     func dfs(_ flights: [Int: [(Int, Int)]], _ src: Int, _ dst: 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, dst, K-1, &cache)
18                 if c != -1 {