|
2 | 2 | Given cities connected by flights [from,to,price], also given src, dst, & k: |
3 | 3 | Return cheapest price from src to dst with at most k stops |
4 | 4 |
|
5 | | - Dijkstra's but modified, normal won't work b/c will discard heap nodes w/o finishing |
6 | | - Modify: need to re-consider a node if dist from source is shorter than what we recorded |
7 | | - But, if we encounter node already processed but # of stops from source is lesser, |
8 | | - Need to add it back to the heap to be considered again |
9 | | -
|
10 | | - Time: O(V^2 log V) -> V = number of cities |
11 | | - Space: O(V^2) |
| 5 | + Minimized implementation of the Bellman-Ford algorithm. |
| 6 | + Loop for #maximum-stops times and, for each flight, update the array of distances if |
| 7 | + there's a new path from the destination to the source having lower cost than the current. |
| 8 | + Time: O(k*n) |
| 9 | + Space: O(n) |
12 | 10 | */ |
13 | 11 |
|
14 | 12 | classSolution { |
15 | 13 | public: |
16 | 14 | intfindCheapestPrice(int n, vector<vector<int>>& flights,int src,int dst,int k) { |
17 | | -// build adjacency matrix |
18 | | - vector<vector<int>>adj(n, vector<int>(n)); |
19 | | -for (int i =0; i < flights.size(); i++) { |
20 | | - vector<int> flight = flights[i]; |
21 | | - adj[flight[0]][flight[1]] = flight[2]; |
22 | | - } |
23 | | - |
24 | | -// shortest distances |
25 | | - vector<int>distances(n, INT_MAX); |
26 | | - distances[src] =0; |
27 | | -// shortest steps |
28 | | - vector<int>currStops(n, INT_MAX); |
29 | | - currStops[src] =0; |
30 | | - |
31 | | -// priority queue -> (cost, node, stops) |
32 | | - priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq; |
33 | | - pq.push({0, src,0}); |
34 | | - |
35 | | -while (!pq.empty()) { |
36 | | -int cost = pq.top()[0]; |
37 | | -int node = pq.top()[1]; |
38 | | -int stops = pq.top()[2]; |
39 | | - pq.pop(); |
40 | | - |
41 | | -// if destination is reached, return cost to get here |
42 | | -if (node == dst) { |
43 | | -return cost; |
44 | | - } |
45 | | - |
46 | | -// if no more steps left, continue |
47 | | -if (stops == k +1) { |
48 | | -continue; |
49 | | - } |
50 | | - |
51 | | -// check & relax all neighboring edges |
52 | | -for (int neighbor =0; neighbor < n; neighbor++) { |
53 | | -if (adj[node][neighbor] >0) { |
54 | | -int currCost = cost; |
55 | | -int neighborDist = distances[neighbor]; |
56 | | -int neighborWeight = adj[node][neighbor]; |
57 | | - |
58 | | -// check if better cost |
59 | | -int currDist = currCost + neighborWeight; |
60 | | -if (currDist < neighborDist || stops +1 < currStops[neighbor]) { |
61 | | - pq.push({currDist, neighbor, stops +1}); |
62 | | - distances[neighbor] = currDist; |
63 | | - currStops[neighbor] = stops; |
64 | | - }elseif (stops < currStops[neighbor]) { |
65 | | -// check if better steps |
66 | | - pq.push({currDist, neighbor, stops +1}); |
67 | | - } |
68 | | - currStops[neighbor] = stops; |
69 | | - } |
| 15 | + vector<int>dist(n, INT_MAX); |
| 16 | + dist[src] =0; |
| 17 | + |
| 18 | +for (int stops =0; stops <= k; ++stops){ |
| 19 | + vector<int> tmp = dist; |
| 20 | +for (auto& flight : flights){ |
| 21 | +int s = flight[0], d = flight[1], p = flight[2]; |
| 22 | +if (dist[s] == INT_MAX) |
| 23 | +continue; |
| 24 | +if (tmp[d] > dist[s] + p) |
| 25 | + tmp[d] = dist[s] + p; |
70 | 26 | } |
| 27 | + dist = tmp; |
71 | 28 | } |
72 | | - |
73 | | -if (distances[dst] == INT_MAX) { |
74 | | -return -1; |
75 | | - } |
76 | | -return distances[dst]; |
| 29 | + |
| 30 | +return dist[dst] == INT_MAX ? -1 : dist[dst]; |
77 | 31 | } |
78 | 32 | }; |