C++-এ থ্রেশহোল্ড দূরত্বে সবচেয়ে কম প্রতিবেশী город খুঁজে বের করা

সমস্যা বিবরণ

মান লেট ০ থেকে n-1 পর্যন্ত নম্বর করা n সংখ্যক শহর আছে। আমাদের কাছে একটি edges অ্যারে রয়েছে যেখানে edges[i] = [fromi, toi, weighti] দুটি শহর fromi এবং toi-এর মধ্যে দ্বিমুখী ও ওজনযুক্ত সংযোগ উপস্থাপন করে। একটি পূর্ণসংখ্যা distance threshold দেওয়া থাকলে, আমাদের সেই শহরটি খুঁজে বের করতে হবে যার থেকে threshold দূরত্বের মধ্যে সবচেয়ে কম সংখ্যক শহর পৌঁছানো যায়। একাধিক takie শহর থাকলে সবচেয়ে বড় নম্বর সম্পন্ন শহরটি ফেরত দিতে হবে।

উদাহরণ

নিচের ইনপুট বিবেচনা করুন:

n = 4, distanceThreshold = 4
edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]]

প্রতিটি শহরের জন্য threshold 4-এর মধ্যে পৌঁছানো যায় এমন প্রতিবেশী শহরগুলো:

শহর ০ → [শহর ১, শহর ২]
শহর ১ → [শহর ০, শহর ২, শহর ৩]
শহর ২ → [শহর ০, শহর ১, শহর ৩]
শহর ৩ → [শহর ১, শহর ২]

শহর ০ এবং ৩-এর দুটি করে প্রতিবেশী রয়েছে। একাধিক সমাধান থাকা কারণে সবচেয়ে বড় নম্বর সম্পন্ন শহর ৩ আউটপুট হিসেবে ফেরত দেওয়া হবে।

সমাধানের পদ্ধতি (ফ্লয়েড-ওয়ারশ্যাল অ্যালগরিদম)

সর্ব-যুগল নিকটতম পথ বের করার জন্য ফ্লয়েড-ওয়ারশ্যাল অ্যালগরিদম ব্যবহার করা হয়। ধাপগুলো নিচে দেওয়া হলো:

n × n আকারের একটি dp ম্যাট্রিক্স সংজ্ঞায়িত করুন এবং সব সেলকে অসীম (infinity) দিয়ে ভরুন।
প্রদত্ত edges থেকে গ্রাফের সन्नিকর্ষ ম্যাট্রিক্স (cost matrix) তৈরি করে dp-তে সংরক্ষণ করুন।
ret = 0 এবং cnt = INT_MAX দিয়ে শুরু করুন।
তিনটি নেস্টেড লুপ (k, i, j) চালিয়ে ফ্লয়েড-ওয়ারশ্যাল алгоритম প্রয়োগ করুন:
- যদি i == j হয় তবে পরবর্তী ইটারেশনে যান।
- যদি dp[i][j] > dp[i][k] + dp[k][j] হয়, তবে dp[i][j] এবং dp[j][i] আপডেট করুন।
প্রতিটি শহর i-এর জন্য threshold-এর মধ্যে পৌঁছানো যায় এমন শহরের সংখ্যা গণনা করুন।
সর্বনিম্ন সংখ্যা (এবং সমান হলে বড় নম্বর)ális শহরটি ret-এ সংরক্ষণ করুন।
ret ফেরত দিন।

C++ বাস্তবায়ন

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

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        // dp ম্যাট্রিক্স ইনিশিয়ালাইজ করা (1e7 = অসীম)
        vector<vector<int>> dp(n, vector<int>(n, 1e7));
        
        // এজগুলো থেকে অ্যাডজেসেন্সি ম্যাট্রিক্স তৈরি
        for (auto& e : edges) {
            int u = e[0], v = e[1], w = e[2];
            dp[u][v] = w;
            dp[v][u] = w;
        }
        
        // ফ্লয়েড-ওয়ারশ্যাল অ্যালগরিদম
        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[i][j] = dp[j][i] = dp[i][k] + dp[k][j];
                    }
                }
            }
        }
        
        // প্রতিটি শহরের জন্য threshold-এর মধ্যে প্রতিবেশী গণনা
        int ret = 0, cnt = INT_MAX;
        for (int i = 0; i < n; i++) {
            int temp = 0;
            for (int j = 0; j < n; j++) {
                if (dp[i][j] <= distanceThreshold) temp++;
            }
            if (temp <= cnt) {
                cnt = temp;
                ret = i;
            }
        }
        return ret;
    }
};

int main() {
    vector<vector<int>> edges = {{0,1,3},{1,2,1},{1,3,4},{2,3,1}};
    Solution ob;
    cout << ob.findTheCity(4, edges, 4); // আউটপুট: 3
    return 0;
}

জটিলতা বিশ্লেষণ

সময় জটিলতা: O(n³) — তিনটি নেস্টেড লুপের কারণে।
স্থান জটিলতা: O(n²) — dp ম্যাট্রিক্স সংরক্ষণের জন্য।

ইনপুট ও আউটপুট উদাহরণ

ইনপুট: 4 [[0,1,3],[1,2,1],[1,3,4],[2,3,1]] 4
আউটপুট: 3