C++ में थ्रेसहोल्ड दूरी पर पड़ोसियों की सबसे छोटी संख्या वाले शहर का पता लगाएं

मान लीजिए कि n शहरों की संख्या 0 से n-1 तक है। यदि हमारे पास सरणी किनारे हैं जहां किनारों [i] =[fromi, toi, weighti] शहरों से i और toi के बीच एक द्विदिश और भारित किनारे का प्रतिनिधित्व करता है, और पूर्णांक दूरी सीमा दी गई है। हमें ऐसे शहरों की सबसे छोटी संख्या वाला शहर ढूंढना है जो किसी रास्ते से पहुंच योग्य हों और जिनकी दूरी सबसे अधिक दूरी की सीमा पर हो, अगर ऐसे एक से अधिक शहर हैं, तो सबसे बड़ी संख्या वाला शहर लौटाएं।

तो अगर इनपुट की तरह है -

n 4 है और दूरी सीमा भी 4 है, तो आउटपुट 3 होगा। ऐसा इसलिए है क्योंकि -

दूरी की दहलीज पर पड़ोसी शहर =प्रत्येक शहर के लिए 4 हैं −

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

शहरों 0 और 3 में 2 पड़ोसी शहर हैं जिनकी दूरी सीमा =4 है, लेकिन हमें शहर 3 को वापस करना होगा क्योंकि इसकी संख्या सबसे बड़ी है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

क्रम n x n के वर्ग मैट्रिक्स को dp कहा जाता है और इसे अनंत से भरें
ग्राफ के आसन्न मैट्रिक्स (लागत मैट्रिक्स) उत्पन्न करें और डीपी में स्टोर करें
रिट:=0 और सीएनटी:=इन्फिनिटी
k के लिए 0 से n - 1 की सीमा में
- मेरे लिए 0 से n - 1 की सीमा में
  - j के लिए 0 से n - 1 की सीमा में
    - अगर i =j, तो अगले पुनरावृत्ति के लिए जाएं
    - अगर dp[i, j]> dp[i, k] + dp[k, j], तब
      - डीपी [जे, आई]:=डीपी [आई, के] + डीपी [के, जे]
      - डीपी [आई, जे]:=डीपी [आई, के] + डीपी [के, जे]
मेरे लिए 0 से n - 1 की सीमा में है
- अस्थायी:=0
- j के लिए 0 से n - 1 की सीमा में
  - अस्थायी:=अस्थायी + 1 जब dp[i, j] <=t, अन्यथा अस्थायी समान रहता है
- अगर अस्थायी <=सीएनटी, फिर सीएनटी:=अस्थायी और सेवानिवृत्त:=i
वापसी रिट

उदाहरण (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