C++でしきい値距離にある近隣の数が最も少ない都市を検索します

0からn-1までの番号が付けられたn個の都市があるとします。 edge [i] =[fromi、toi、weighti]である配列エッジがある場合、都市fromiとtoiの間の双方向の重み付きエッジを表し、整数の距離しきい値が与えられます。あるパスを介して到達可能で、距離が最大で距離のしきい値である都市の数が最も少ない都市を見つける必要があります。そのような都市が複数ある場合は、最も多い都市を返します。

したがって、入力が-

nが4で、距離のしきい値も4の場合、出力は3になります。これは-

各都市の距離しきい値=4にある隣接する都市は、-

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

都市0と3には、距離のしきい値=4で2つの隣接する都市がありますが、都市3の数が最も多いため、都市3を返す必要があります。

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

• dpと呼ばれる次数nxnの正方行列を定義し、これを無限大で埋めます

• グラフの隣接行列（コスト行列）を生成し、dpに格納します

• ret：=0およびcnt：=無限大

• 0からn–1の範囲のkの場合

  • 0からn–1の範囲のiの場合

    • 0からn–1の範囲のjの場合

      • i =jの場合、次の反復に進みます

      • dp [i、j]> dp [i、k] + dp [k、j]の場合、

        • dp [j、i]：=dp [i、k] + dp [k、j]

        • dp [i、j]：=dp [i、k] + dp [k、j]

• 0からn-1の範囲のiの場合

  • temp：=0

  • 0からn–1の範囲のjの場合

    • temp：=temp + 1（dp [i、j] <=tの場合、それ以外の場合、tempは同じままです

  • temp <=cntの場合、cnt：=tempおよびret：=i

• retを返す

例（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