পাইথনে নাগরিকদের মার্কেট এক্সেসের জন্য মিনিমাম খরচ বের করা

n সিটি এবং m রোড আছে। মার্কেট বানাতে খরচ y, রোড বানাতে খরচ x। প্রতিটি সিটির নাগরিকের কাছে মার্কেট এক্সেস দিতে হবে (সিটি-তে মার্কেট থাকবে অথবা রোড দিয়ে মার্কেটवाले সিটিতে যেতে পারবে)। মিনিমাম টোটাল খরচ বের করতে হবে।

উদাহরণ

ইনপুট: n = 4, m = 3, x = 1, y = 2, cities = [[1,2],[2,3],[3,4]]

আউটপুট: 4

সিটি ১-এ মার্কেট বানিয়ে (খরচ ২), সিটি ১ থেকে ৩ ও ৪-এ রোড বানালে (খরচ ১+১=২) মোট ৪।

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

1. যদি x <= y: সব সিটির সাথে রোড বানানো সস্তা → রিটার্ন n * x।
2. অন্যথায়:
   • অ্যাডজেসেন্সি লিস্ট বানান।
   • BFS/DFS দিয়ে কানেক্টেড কম্পোনেন্ট খুঁজুন।
   • প্রতিটি কম্পোনেন্টের জন্য ১টি মার্কেট (খরচ y) এবং বাকি নোডগুলোকে রোড দিয়ে কানেক্ট করুন (খরচ x)।
   • টোটাল খরচ = কম্পোনেন্ট_সংখ্যা * y + (n - কম্পোনেন্ট_সংখ্যা) * x।

পাইথন ইমপ্লিমেন্টেশন

from collections import defaultdict, deque

def solve(n, m, x, y, cities):
    if x <= y:
        return n * x
    adj_list = defaultdict(list)
    for city in cities:
        city1, city2 = city[0], city[1]
        adj_list[city1].append(city2)
        adj_list[city2].append(city1)
    visited = [True] * (n + 1)
    value = 0
    dq = deque()
    for cur in range(1, n + 1):
        if visited[cur]:
            value += x  # প্রথম নোডে মার্কেট বানানো হয়েছে ধরে (x/y মিক্স করা হয়েছে)
            dq.append(cur)
            visited[cur] = False
            while dq:
                node = dq.popleft()
                for nei in adj_list[node]:
                    if visited[nei]:
                        dq.append(nei)
                        visited[nei] = False
                        value += y  # রোড বানানো খরচ
    return value

# টেস্ট
print(solve(4, 3, 1, 2, [[1, 2], [2, 3], [3, 4]]))  # আউটপুট: 4

ইনপুট

4, 3, 2, 1, [[1, 2], [2, 3], [3, 4]]

আউটপুট

4