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

发布时间：2020-12-14 05:01:47 所属栏目：百科来源：网络整理

导读：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 c

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 = 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?个城市通过?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 = 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,k: k,vertex: neighbor,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,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,_ 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.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,_ 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,_ 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,_ 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,_ 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,&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,_ 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] = c
20                    m = min(m ?? Int.max,c+f.1) 
21                 }  else {
22                     cache[f.0][K] = -1
23                 }
24             }
25         }
26         return m ?? -1
27     }
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 : res
14     }
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             return
23         }
24 
25         if let lowest = dp[start] {
26             if lowest < cost {
27                 return
28             }
29         }
30         dp[start] = cost
31 
32         var forwardCost = Int.max
33         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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!