C++で解く「K回以内の乗り継ぎで最安となるフライト」問題

n個の都市がm本のフライト（路線）で結ばれている状況を考えてみましょう。各フライトは出発地 u から到着地 v へ、料金 w で移動できるものとします。すべての都市とフライトの情報に加え、出発都市 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 となります。これは「0 → 1 → 2」という経路（100 + 100 = 200）が、1回の乗り継ぎという条件を満たす最安ルートだからです。直行便の「0 → 2」（料金500）は条件内で利用できますが、より高額なため採用されません。

解法のアプローチ

この問題は、ダイクストラ法をベースにしつつ、「乗り継ぎ回数」という制約を考慮する必要がある点がポイントです。通常のダイクストラ法では最短距離（最安料金）のみを追跡しますが、ここでは通過した経由地の数ごとに最小コストを管理することで制約に対応します。

具体的には、以下の手順で解きます。

1. ノード番号・乗り継ぎ回数・累積コストを保持できる Data 構造体を定義する。
2. 2次元配列 cost を用意し、(n + 1) × (K + 10) のサイズで無限大（INT_MAX）で初期化する。cost[都市][乗り継ぎ回数] がその状態での最小コストを表す。
3. 隣接リストとして機能する配列 graph を作成し、各フライト情報 {v, 料金} を登録していく。
4. 優先度付きキュー（最小ヒープ）q を定義し、初期状態として Data(src, 0, 0) を挿入する。また cost[src][0] = 0 とする。
5. キューが空になるまで以下を繰り返す。
   • キューの先頭要素を取り出し、現在のノード curr と乗り継ぎ回数 dist を取得する。
   • curr が目的地 dst なら、その時点のコストを即座に返す（優先度付きキューなので、これが最安値であることが保証される）。
   • 乗り継ぎ回数を1増やし、K + 1 を超える場合は以降の探索をスキップする。
   • curr に隣接する各ノードについて、cost[隣接ノード][dist] が cost[curr][dist - 1] + 運賃 より大きければ更新し、新しい状態をキューに追加する。
6. キューが空になっても目的地に到達できなければ、-1 を返す。

C++による実装例

それでは、実際の実装を見ていきましょう。

#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

計算量と補足

このアルゴリズムの計算量は、都市数を n、フライト数を E、乗り継ぎ上限を K としたとき、おおよそ O(E・K・log(E・K)) となります。各エッジは高々 K+1 回ずつ評価され、優先度付きキューへの挿入・削除には対数時間がかかるためです。

また、同じ都市でも「到達したときの乗り継ぎ回数」が異なれば別の状態として扱う点が重要です。これにより、乗り継ぎ回数の制約を守りながら、正しい最安値を求められます。目的地に到達した時点で即座に結果を返しているのは、コスト昇順の優先度付きキューを使っているため、最初に取り出した状態が必ず最安であることが保証されているからです。