C++-এ সব নোড ভিজিট করার শর্টেস্ট পাথ

সমস্যা বিবরণ

অনডিরেক্টেড কানেক্টেড গ্রাফ দেওয়া থাকলে (নোড ০ থেকে N-১)। সব নোড কমপক্ষে একবার ভিজিট করার শর্টেস্ট পাথের দৈর্ঘ্য বের করতে হবে। যেকোনো নোড থেকে শুরু/শেষ করা যায়, নোড/এজ পুনরাবৃত্তি করা যায়।

উদাহরণ

graph = [[1],[0,2,4],[1,3,4],[2],[1,2]] → আউটপুট = 4 (পাথ: [0,1,4,2,3])

সমাধান পদ্ধতি

• BFS + বিটমাস্ক DP ব্যবহার করা হয়।
• স্টেট = (ভিজিটেড মাস্ক, বর্তমান নোড)।
• শুরুতে সব নোড থেকে মাস্ক (1<
• লেভেল বাই লেভেল BFS, লক্ষ্য মাস্ক = (1<
• ভিজিটেড [node][mask] দিয়ে ডুপ্লিকেট এড়ানো হয়।

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

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

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    int shortestPathLength(vector<vector<int>> &graph) {
        queue<vector<int>> q;
        int n = graph.size();
        int req = (1 << n) - 1;
        map<int, set<int>> visited;
        
        for (int i = 0; i < n; i++)
            q.push({ (1 << i), i });
        if (n == 1) return 0;
        
        for (int lvl = 1; !q.empty(); lvl++) {
            int sz = q.size();
            while (sz--) {
                vector<int> curr = q.front(); q.pop();
                for (int u : graph[curr[1]]) {
                    int newMask = curr[0] | (1 << u);
                    if (newMask == req) return lvl;
                    if (visited[u].count(newMask)) continue;
                    visited[u].insert(newMask);
                    q.push({ newMask, u });
                }
            }
        }
        return -1;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1},{0,2,4},{1,3,4},{2},{1,2}};
    cout << ob.shortestPathLength(v);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {{1},{0,2,4},{1,3,4},{2},{1,2}}

আউটপুট: 4