C++에서 K 정류장 내 가장 저렴한 항공편

m개의 항공편으로 연결된 n개의 도시가 있다고 가정합니다. 각 항공편은 u에서 시작하여 가격이 w인 v에 도착합니다. 시작 도시 src 및 목적지 dst와 함께 모든 도시와 항공편이 있는 경우 여기에서 우리의 임무는 최대 k 정거장으로 src에서 dst까지 가장 저렴한 가격을 찾는 것입니다. 해당 경로가 없으면 -1을 반환합니다.

따라서 입력이 n =3, edge =[[0,1,100],[1,2,100],[0,2,500]], src =0, dst =2, k =1인 경우 출력은 다음과 같습니다. 200

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• Data라고 하는 하나의 데이터 구조를 생성합니다. 이 구조는 node, dist 및 val을 보유할 수 있습니다.

• 하나의 2D 어레이 비용 정의

• 비용 :=하나의 2D 배열 순서 (n + 1) x (K + 10) 무한대로 채우기

• 하나의 3D 배열 그래프 정의

• 초기화 i :=0의 경우 i <비행 크기일 때 업데이트(i를 1만큼 증가), 수행 -

  • u :=항공편[i, 0]

  • v :=항공편[i, 1]

  • 그래프[u]의 끝에 { v, flight[i, 2] } 삽입

• 하나의 우선순위 큐 정의 q

• 데이터(src, 0, 0)를 q에 삽입

• 비용[src, 0] :=0

• as :=-1

• 동안(q가 비어 있지 않음) -

  를 수행합니다.

  • temp :=q의 최상위 요소

  • curr :=temp.node

  • q에서 요소 삭제

  • dist :=temp.dist

  • curr이 dst와 같으면 -

    • 반환 temp.cost

  • (dist를 1만큼 증가)

  • dist> K + 1이면 -

    • 다음 부분은 무시하고 다음 반복으로 건너뜁니다.

  • for initialize i :=0, i

    • 이웃 :=그래프[curr, i, 0]

    • 비용[neighbour, dist]> 비용[curr, dist - 1] + graph[curr, i, 1]이면 -

      • 비용[neighbour, dist] :=비용[curr, dist - 1] + 그래프[curr, i, 1]

      • 데이터(이웃, dist, 비용[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