Các chuyến bay giá rẻ nhất trong phạm vi K dừng bằng C ++

Giả sử chúng ta có n thành phố được kết nối bởi m chuyến bay. Mỗi chuyến bay xuất phát từ u và đến v với giá w. Nếu chúng ta có tất cả các thành phố và chuyến bay, cùng với thành phố xuất phát src và điểm đến là dst, ở đây nhiệm vụ của chúng ta là tìm mức giá rẻ nhất từ src đến dst với tối đa k điểm dừng. Nếu không có tuyến nào như vậy, hãy trả về -1.

Vì vậy, nếu đầu vào là n =3, các cạnh =[[0,1,100], [1,2,100], [0,2.500]], src =0, dst =2, k =1, thì đầu ra sẽ là 200

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Tạo một cấu trúc dữ liệu có tên là Data, cấu trúc này có thể chứa nút, dist và val
Xác định chi phí cho một mảng 2D
cost:=một mảng 2D theo thứ tự (n + 1) x (K + 10) điền vào vô cực
Xác định một biểu đồ mảng 3D
để khởi tạo i:=0, khi tôi
- u:=chuyến bay [i, 0]
- v:=chuyến bay [i, 1]
- chèn {v, chuyến bay [i, 2]} vào cuối biểu đồ [u]
xác định một hàng đợi ưu tiên q
chèn Dữ liệu (src, 0, 0) vào q
chi phí [src, 0]:=0
ans:=-1
while (không phải q trống), do -
- temp:=phần tử hàng đầu của q
- curr:=temp.node
- xóa phần tử khỏi q
- dist:=temp.dist
- nếu curr giống với dst, thì -
  - trả về temp.cost
- (tăng dist lên 1)
- nếu dist> K + 1, thì -
  - Bỏ qua phần sau, chuyển sang phần tiếp theo
- để khởi tạo i:=0, khi i
  - hàng xóm:=graph [curr, i, 0]
  - nếu cost [Láng giềng, dist]> cost [curr, dist - 1] + graph [curr, i, 1] thì -
    - cost [Neighbor, dist]:=cost [curr, dist - 1] + graph [curr, i, 1]
    - chèn Dữ liệu (hàng xóm, phân phối, chi phí [hàng xóm, chi phí]) vào q
trả về -1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
struct Data{
   int node, dist, cost;
   Data(int a, int b, int c){
      node = a;
      dist = b;
      cost = c;
   }
};
struct Comparator{
   bool operator() (Data a, Data b) {
      return !(a.cost < b.cost);
   }
};
class Solution {
public:
   vector<vector<int>> cost;
   int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
      cost = vector<vector<int> >(n + 1, vector<int>(K + 10, INT_MAX));
      vector<vector<int> > graph[n];
      for (int i = 0; i < flights.size(); i++) {
         int u = flights[i][0];
         int v = flights[i][1];
         graph[u].push_back({ v, flights[i][2] });
      }
      priority_queue<Data, vector<Data>, Comparator> q;
      q.push(Data(src, 0, 0));
      cost[src][0] = 0;
      int ans = -1;
      while (!q.empty()) {
         Data temp = q.top();
         int curr = temp.node;
         q.pop();
         int dist = temp.dist;
         if (curr == dst)
            return temp.cost;
         dist++;
         if (dist > K + 1)
            continue;
         for (int i = 0; i < graph[curr].size(); i++) {
            int neighbour = graph[curr][i][0];
            if (cost[neighbour][dist] > cost[curr][dist - 1] + graph[curr][i][1]) {
               cost[neighbour][dist] = cost[curr][dist - 1] + graph[curr][i][1];
               q.push(Data(neighbour, dist, cost[neighbour][dist]));
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,100},{1,2,100},{0,2,500}};
   cout << (ob.findCheapestPrice(3, v, 0, 2, 1));
}

Đầu vào

3, {{0,1,100},{1,2,100},{0,2,500}}, 0, 2, 1

Các chuyến bay giá rẻ nhất trong phạm vi K dừng bằng C ++

Ví dụ

Đầu vào

Đầu ra