पायथन में भारित ग्राफ से न्यूनतम संभव लागत ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास edges नामक पूर्णांकों की एक 2D सूची है जो एक अविभाजित ग्राफ का प्रतिनिधित्व करती है। इनपुट में हर पंक्ति एक एज [u, v, w] दर्शाती है जिसका अर्थ है नोड्स u और v जुड़े हुए हैं और एज का वजन w है। ग्राफ में 0 से n-1 तक n नोड्स होते हैं।

यहां एक पथ की लागत को पथ में किनारों की संख्या और पथ में किसी भी एज के अधिकतम वजन के गुणनफल के रूप में परिभाषित किया गया है। हमें नोड 0 से नोड n-1 तक न्यूनतम संभव लागत ज्ञात करनी है, या यदि ऐसा कोई पथ मौजूद नहीं है तो उत्तर -1 घोषित करें।

इसलिए, यदि इनपुट edges = [[0, 2, 100], [1, 2, 200], [1, 3, 100], [2, 3, 300]] जैसा है, तो आउटपुट 600 होगा।

हल करने के चरण

• graph := एक नया मैप

• weights := एक नया मैप

• max_weight := 0

• N := 0

• edges में प्रत्येक u, v, w के लिए, करें

  • v को graph[u] के अंत में डालें

  • u को graph[v] के अंत में डालें

  • weights[u, v] := w

  • weights[v, u] := w

  • N := N, u + 1, v + 1 का अधिकतम

  • max_weight := max_weight, w का अधिकतम

• result := infinity

• जब तक max_weight >= 0, करें

  • d, weight := bfs(0, max_weight)

  • यदि d >= 0, तो

    • result := result और d * weight का न्यूनतम

    • max_weight := weight - 1

  • अन्यथा, लूप समाप्त करें

• यदि result < infinity तो result लौटाएं अन्यथा -1

• bfs() फ़ंक्शन परिभाषित करें। यह root, weight_cap लेगा

  • target := N - 1

  • Q := root, 0, 0 वाले एक डीक्यू

  • visited := [False] * N

  • visited[0] := True

  • जब तक Q खाली नहीं है, करें

    • v, d, current_weight := Q से अंतिम तत्व हटाएं

    • यदि v, N - 1 के समान है, तो d, current_weight लौटाएं

    • graph[v] में प्रत्येक w के लिए, करें

      • यदि visited[w] शून्येतर है, तो अगले इटरेशन पर जारी रखें

      • new_weight := weights[v, w]

      • यदि new_weight <= weight_cap, तो

        • visited[w] := True

        • (w, d + 1, current_weight और new_weight का अधिकतम) को Q के बाएं में डालें

  • -1, -1 लौटाएं

उदाहरण

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]]

आउटपुट

600