เที่ยวบินที่ถูกที่สุดภายใน K หยุดใน C++

สมมติว่าเรามี n เมืองที่เชื่อมต่อกันด้วยเที่ยวบิน m แต่ละเที่ยวบินเริ่มต้นจากคุณและมาถึงที่ v ด้วยราคา w หากเรามีเมืองและเที่ยวบินทั้งหมด พร้อมกับเมืองเริ่มต้น src และ dst ปลายทาง หน้าที่ของเราคือค้นหาราคาที่ถูกที่สุดจาก src ถึง dst โดยมีจุดจอดสูงสุด k แห่ง หากไม่มีเส้นทางดังกล่าว ให้กลับ -1

ดังนั้น หากอินพุตเป็น n =3, edge =[[0,1,100],[1,2,100],[0,2,500]], src =0, dst =2, k =1 ผลลัพธ์จะเป็น 200

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างโครงสร้างข้อมูลที่เรียกว่า Data ซึ่งสามารถเก็บ node, dist และ val ได้

• กำหนดต้นทุนอาร์เรย์ 2 มิติหนึ่งรายการ

• ราคา :=หนึ่งอาร์เรย์ 2 มิติของการสั่งซื้อ (n + 1) x (K + 10) เติมด้วยอินฟินิตี้

• กำหนดกราฟอาร์เรย์ 3 มิติหนึ่งกราฟ

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของเที่ยวบิน อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ −

  • u :=เที่ยวบิน[i, 0]

  • v :=เที่ยวบิน[i, 1]

  • แทรก { v, เที่ยวบิน[i, 2] } ที่ส่วนท้ายของกราฟ[u]

• กำหนดลำดับความสำคัญหนึ่งคิว q

• แทรก Data(src, 0, 0) ลงใน q

• ราคา[src, 0] :=0

• ตอบ :=-1

• ในขณะที่ (ไม่ใช่ q ว่างเปล่า) ทำ -

  • temp :=องค์ประกอบด้านบนของ q

  • curr :=temp.node

  • ลบองค์ประกอบออกจาก q

  • dist :=temp.dist

  • ถ้าสกุลเงินเหมือนกับ dst แล้ว −

    • คืนค่า temp.cost

  • (เพิ่ม dist ขึ้น 1)

  • ถ้า dist> K + 1 แล้ว −

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของกราฟ[curr] อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • เพื่อนบ้าน :=กราฟ[curr, i, 0]

    • ถ้า cost[neighbour, dist]> cost[curr, dist - 1] + graph[curr, i, 1] แล้ว −

      • cost[neighbour, dist] :=cost[curr, dist - 1] + กราฟ[curr, i, 1]

      • แทรก Data(neighbour, dist, cost[neighbour, dist]) ลงใน q

• กลับ -1

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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));
}

อินพุต

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

ผลลัพธ์

200