C++ में थ्रेशोल्ड दूरी पर सबसे कम पड़ोसियों वाला शहर ढूंढना

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

उदाहरण के लिए, अगर इनपुट है:

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

distanceThreshold = 4 पर प्रत्येक शहर के पड़ोसी शहर हैं:

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

शहर 0 और 3 के distanceThreshold = 4 पर 2 पड़ोसी शहर हैं, लेकिन हमें शहर 3 लौटाना है क्योंकि इसकी संख्या सबसे बड़ी है।

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

• ऑर्डर n x n का एक स्क्वायर मैट्रिक्स dp डिफाइन करें और इसे इनफिनिटी से भरें

• ग्राफ का एडजेसेंसी मैट्रिक्स (कॉस्ट मैट्रिक्स) जनरेट करें और dp में स्टोर करें

• ret := 0 और cnt := इनफिनिटी

• k को 0 से n-1 तक लूप करें:

  • i को 0 से n-1 तक लूप करें:

    • j को 0 से n-1 तक लूप करें:

      • अगर 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]

• i को 0 से n-1 तक लूप करें:

  • temp := 0

  • j को 0 से n-1 तक लूप करें:

    • 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;
    }
};

int 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