পাইথনে ওয়েটেড গ্রাফ থেকে ন্যূনতম খরচের পথ বের করা (এজ সংখ্যা × সর্বোচ্চ ওয়েট)

একটি অনডিরেক্টেড গ্রাফ দেওয়া আছে edges = [[u, v, w], ...] আকারে। নোড ০ থেকে নোড n-1 পর্যন্ত যেতে হবে। পথের খরচ = (পথে এজ সংখ্যা) × (পথে সর্বোচ্চ ওয়েট)। ন্যূনতম খরচ বের করতে হবে, পথ না থাকলে -১।

উদাহরণ: edges = [[0,2,100],[1,2,200],[1,3,100],[2,3,300]] → আউটপুট 600।

সমাধানের ধাপসমূহ (BFS + বাইনারি সার্চ ওয়েটের ওপর)

গ্রাফ ও ওয়েট ম্যাপ বানান। max_weight = সর্বোচ্চ ওয়েট। N = নোড সংখ্যা।
bfs(root, weight_cap) ফাংশন: শুধু weight_cap এর নিচের এজ দিয়ে BFS চালিয়ে টার্গেটে পৌঁছালে (distance, actual_max_weight) রিটার্ন করে।
weight_cap = max_weight থেকে ০ পর্যন্ত কমিয়ে যান। প্রতিবার BFS করুন। পথ পেলে result = min(result, d * weight) আপডেট করুন এবং weight_cap = weight - 1 করুন (কারণ আমরা ছোট ওয়েট চাই)।
পথ না পাওয়া পর্যন্ত লুপ চালান। ফাইনাল result বা -১ রিটার্ন করুন।

পাইথন কোড উদাহরণ

from collections import defaultdict, deque
class Solution:
    def solve(self, edges):
        graph = defaultdict(list)
        weights = {}
        max_weight = 0
        N = 0
        for u, v, w in edges:
            graph[u].append(v)
            graph[v].append(u)
            weights[u, v] = w
            weights[v, u] = w
            N = max(N, u + 1, v + 1)
            max_weight = max(max_weight, w)
        def bfs(root, weight_cap):
            target = N - 1
            Q = deque([(root, 0, 0)])
            visited = [False] * N
            visited[0] = True
            while Q:
                v, d, current_weight = Q.pop()
                if v == N - 1:
                    return d, current_weight
                for w in graph[v]:
                    if visited[w]:
                        continue
                    new_weight = weights[v, w]
                    if new_weight <= weight_cap:
                        visited[w] = True
                        Q.appendleft((w, d + 1, max(current_weight, new_weight)))
            return -1, -1
        result = float("inf")
        while max_weight >= 0:
            d, weight = bfs(0, max_weight)
            if d >= 0:
                result = min(result, d * weight)
                max_weight = weight - 1
            else:
                break
        return result if result < float("inf") else -1

ob = Solution()
print(ob.solve([
    [0, 2, 100],
    [1, 2, 200],
    [1, 3, 100],
    [2, 3, 300]
]))

ইনপুট

[[0,2,100],[1,2,200],[1,3,100],[2,3,300]]