【C++】しきい値距離以内で到達できる都市数が最も少ない都市を求める方法

問題概要

0からn-1までの番号が付けられたn個の都市があるとします。配列edgesが与えられ、edges[i] = [from_i, to_i, weight_i] は都市from_iとto_iの間を結ぶ双方向の重み付き辺を表します。さらに、整数の距離しきい値(distance threshold)が与えられます。

このとき、何らかの経路を辿って到達でき、かつその距離がしきい値以下となる都市の数が最も少ない都市を求めてください。該当する都市が複数存在する場合は、その中で最も番号の大きい都市を返します。

入力例

次のような入力を考えてみましょう。

n = 4、距離しきい値も4であるとき、出力は3になります。その理由は以下の通りです。

各都市について、距離しきい値4以内で到達できる隣接都市は次のようになります。

C0 -> [C1, C2]
C1 -> [C0, C2, C3]
C2 -> [C0, C1, C3]
C3 -> [C1, C2]

都市0と都市3は、しきい値4以内の隣接都市が2つずつと同数ですが、番号が大きい方の「都市3」を返す必要があります。

解法のアプローチ(ワーシャル・フロイド法)

この問題は、全ペア間の最短距離を一度に求められる「ワーシャル・フロイド法(Floyd-Warshall algorithm)」を使うことで効率的に解けます。具体的には、以下の手順で進めます。

• n×nの正方行列dpを定義し、すべての要素を無限大(十分に大きな値)で初期化します
• グラフの隣接行列(コスト行列)を作成し、dpに格納します
• 答えを格納するretを0、到達都市数の最小値を記録するcntを無限大で初期化します
• k、i、jをそれぞれ0からn-1まで動かす三重ループで以下を繰り返します
  • i = jの場合は次の反復へスキップします
  • dp[i][j] > dp[i][k] + dp[k][j] が成り立つ場合、中継点kを経由する経路の方が短いことを意味するため、dp[i][j]とdp[j][i]をdp[i][k] + dp[k][j]で更新します
• 各都市iについて、距離がしきい値t以下となる都市の数tempを数えます
• tempがcnt以下であれば、cnt := temp、ret := iと更新します(同数の場合は条件式が「以下」になっているため、番号の大きい都市が自動的に採用されます)
• 最後にretを返します

このアルゴリズムの計算量はO(n³)です。nが数百程度までの規模であれば十分に高速に動作するため、全ペア最短経路が必要なこの種の問題には最適な選択肢となります。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findTheCity(int n, vector<vector<int>>& e, int t) {
      vector < vector <int> > dp(n, vector <int>(n, 1e7));
      for(int i = 0; i < e.size(); i++){
         int u = e[i][0];
         int v = e[i][1];
         int w = e[i][2];
         dp[u][v] = w;
         dp[v][u] = w;
      }
      int ret = 0;
      int cnt = INT_MAX;
      for(int k = 0; k < n; k++){
         for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
               if(i == j) continue;
               if(dp[i][j] > dp[i][k] + dp[k][j]){
                  dp[j][i] = dp[i][j] = (dp[i][k] + dp[k][j]);
               }
            }
         }
      }
      for(int i = 0; i < n; i++){
         int temp = 0;
         for(int j = 0; j < n; j++){
            temp += (dp[i][j] <= t);
         }
         if(temp <= cnt){
            cnt = temp;
            ret = i;
         }
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v = {{0,1,3},{1,2,1},{1,3,4},{2,3,1}};
   Solution ob;
   cout << (ob.findTheCity(4, v, 4));
}

入力

4
[[0,1,3],[1,2,1],[1,3,4],[2,3,1]]
4

出力

3

まとめ

本記事では、しきい値距離以内で到達できる都市数が最も少ない都市を求める問題を、ワーシャル・フロイド法を用いて解く方法を解説しました。全ペア間の最短距離をO(n³)で計算した後、各都市からの到達数を数えて比較するだけなので、実装も非常にシンプルです。同数の都市が存在する場合に番号の大きい方を返す、という条件の扱い方にも注意しておきましょう。