C++のKストップ内で最も安いフライト

m個のフライトで接続されたn個の都市があるとします。各フライトはuから始まり、価格wでvに到着します。すべての都市とフライトがあり、開始都市srcと目的地dstがある場合、ここでのタスクは、最大kストップでsrcからdstまでの最も安い価格を見つけることです。そのようなルートがない場合は、-1を返します。

したがって、入力がn =3、edges =[[0,1,100]、[1,2,100]、[0,2,500]]、src =0、dst =2、k =1の場合、出力は次のようになります。 200

これを解決するには、次の手順に従います-

• Dataと呼ばれる1つのデータ構造を作成します。これは、node、dist、およびvalを保持できます

• 1つの2Dアレイコストを定義する

• コスト：=次数（n + 1）x（K + 10）の1つの2D配列これを無限大で埋める

• 1つの3D配列グラフを定義する

• 初期化i：=0の場合、i <フライトのサイズの場合、更新（iを1増やします）、実行-

  • u：=フライト[i、0]

  • v：=フライト[i、1]

  • グラフの最後に{v、flights [i、2]}を挿入します[u]

• 1つの優先キューを定義するq

• Data（src、0、0）をq

  に挿入します

• cost [src、0]：=0

• ans：=-1

• （qが空ではない）間、-

  • temp：=qの最上位要素

  • curr：=temp.node

  • qから要素を削除

  • dist：=temp.dist

  • currがdstと同じ場合、-

    • 戻り温度コスト

  • （距離を1増やします）

  • dist> K + 1の場合、-

    • 次の部分を無視し、次の反復にスキップします

  • 初期化i：=0の場合、i

    • 隣人：=グラフ[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