電車で出発駅から目的駅へ到達する最小時間を求めるC++プログラム

問題概要

n個の駅がm本の路線で結ばれているとします。駅には1からnまでの番号が付けられており、すべての路線は双方向に通行可能です。ここで、出発駅srcから目的駅dstへ移動することを考えます。i番目の路線の両端の駅は配列「roads」で与えられ、roads[i]は{station1, station2}という形式で表されます。

各駅からは、その駅と接続しているすべての駅へ向かう列車が、時間kjの倍数の時刻に発車します。また、各列車が接続先の駅に到達するまでにはtjの時間がかかります。これらの値は配列「departure」で与えられ、各要素は{tj, kj}という形式です。求めるのは、srcからdstに到達するまでの最小時間です。乗り換えは何度でも可能で、乗り換えにかかる時間は無視できるものとします。

入力例と出力例

たとえば、入力が n = 4、m = 3、src = 1、dst = 4、roads = {{1, 2}, {2, 4}, {3, 4}}、departure = {{2, 1}, {3, 5}, {7, 6}} の場合、出力は 8 になります。

この場合の移動の流れは次のとおりです。まず駅1で時刻0発の列車に乗り、2の時間をかけて駅2に到着します。続いて駅2で時刻5発の列車に乗り換え、3の時間をかけて駅4に到着します。したがって、合計所要時間は (5 + 3) = 8 となります。

解法の考え方

この問題は、ダイクストラ法を応用することで効率的に解けます。通常の最短経路問題との違いは、各路線に「列車がkjの倍数の時刻にしか発車しない」という制約がある点です。ある駅に時刻tに到着した場合、次に乗車できるのは、t以上でkjの倍数となる最も早い時刻の列車です。

実装では時刻を負の値として管理し、最大ヒープ型の優先度付きキューを利用することで、「最も早く到着できる状態」から順に探索を進めます。これにより、各駅へ最も早く到着できる時刻を確定的に求めることができます。

アルゴリズムの手順

この問題を解くために、以下の手順に従います。

src := src - 1
dst := dst - 1
タプルを格納する新しい配列 graph[n] を定義
i := 0 で初期化し、i < m の間、i を 1 ずつ増やしながら以下を実行する：
   a := roads[i] の第1要素 - 1
   b := roads[i] の第2要素 - 1
   t := departure[i] の第1要素
   k := departure[i] の第2要素
   graph[a] の末尾にタプル (b, t, k) を追加
   graph[b] の末尾にタプル (a, t, k) を追加
サイズ n の配列 dp を値 -9999 で初期化して定義
ペアを格納する優先度付きキュー priq を定義
dp[src] := 0
priq の末尾にペア (-dp[src], src) を挿入
priq が空でない間、以下を繰り返す：
   (w, a) := priq の最大値を含むタプル
   priq から先頭要素を削除
   a が dst と等しい場合：
      -w を返す
   w < dp[a] の場合：
      以下を無視して次の反復へスキップ
   graph[a] の各要素 v について以下を実行する：
      (b, t, k) を含むタプルを取り出す
      weight := (w - k + 1) / k * k - t
      weight > dp[b] の場合：
         dp[b] := weight
         priq の末尾にペア (weight, b) を挿入
-1 を返す

実装例（C++）

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int n, int m, int src, int dst, vector<pair<int, int>> roads, vector<pair<int, int>> departure){
   src -= 1; 
   dst -= 1;
   vector<tuple<int, int, int>> graph[n];
   int a, b;
   int t, k;
   for(int i = 0; i < m; i++){
      a = roads[i].first - 1;
      b = roads[i].second - 1;
      t = departure[i].first;
      k = departure[i].second;
      graph[a].emplace_back(b, t, k);
      graph[b].emplace_back(a, t, k);
   }
   vector<int> dp(n, -9999);
   priority_queue<pair<int, int>> priq; 
   dp[src] = 0;
   priq.push(make_pair(-dp[src], src));
   int w;
   while(not priq.empty()){
      tie(w, a) = priq.top();
      priq.pop(); if(a == dst){
         return -w;
      }
      if(w < dp[a]) 
         continue;
      for(auto &v: graph[a]){
         tie(b, t, k) = v;
         int weight = (w - k + 1) / k * k - t; 
         if(weight > dp[b]){
            dp[b] = weight;
            priq.push(make_pair(weight, b));
         }
      }
   }
   return -1;
}
int main() {
   int n = 4, m = 3, src = 1, dst = 4;
   vector<pair<int, int>>
   roads = {{1, 2}, {2, 4}, {3, 4}},
   departure = {{2, 1}, {3, 5}, {7, 6}};
   cout<< solve(n, m, src, dst, roads, departure);
   return 0;
}

入力

4, 3, 1, 4, {{1, 2}, {2, 4}, {3, 4}}, {{2, 1}, {3, 5}, {7, 6}}

出力

8

計算量

優先度付きキューを用いたダイクストラ法と同様に、駅数をn、路線数をmとすると、このアルゴリズムの計算量は O((n + m) log n) 程度になります。発車時刻の制約があるグラフ問題においても、到着時刻が単調に増加するため、ダイクストラ法の性質がそのまま成り立つ点がポイントです。