পাইথনে ওয়েটেড গ্রাফ থেকে সম্ভাব্য ন্যূনতম খরচ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে প্রান্ত নামক পূর্ণসংখ্যার একটি 2D তালিকা রয়েছে যা একটি অনির্দেশিত গ্রাফের উপস্থাপনা। ইনপুটের প্রতিটি সারি একটি প্রান্তকে প্রতিনিধিত্ব করে [u, v, w] মানে u এবং v নোড সংযুক্ত এবং প্রান্তটির ওজন w আছে। গ্রাফটি 0 থেকে n-1 পর্যন্ত n নোড নিয়ে গঠিত।

একটি পথের খরচ এখানে প্রান্তের সংখ্যার গুণফল এবং পথের যেকোনো প্রান্তের সর্বোচ্চ ওজন হিসাবে সংজ্ঞায়িত করা হয়েছে। আমাদের নোড 0 থেকে নোড n-1 পর্যন্ত সম্ভাব্য ন্যূনতম খরচ খুঁজে বের করতে হবে, অথবা এই ধরনের কোনো পথ না থাকলে আমরা উত্তরটিকে -1 হিসাবে ঘোষণা করি৷

So, if the input is like edges = [
   [0, 2, 100],
   [1, 2, 200],
   [1, 3, 100],
   [2, 3, 300]
], then the output will be 600

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• গ্রাফ :=একটি নতুন মানচিত্র

• ওজন :=একটি নতুন মানচিত্র

• সর্বোচ্চ_ওজন :=0

• N :=0

• প্রতিটি জন্য u, v, w প্রান্তে, do

  • গ্রাফ[u]

    -এর শেষে v সন্নিবেশ করান

  • গ্রাফের শেষে u ঢোকান[v]

  • ওজন [u, v] :=w

  • ওজন [v, u] :=w

  • N :=সর্বাধিক N, u + 1, v + 1

  • সর্বোচ্চ_ওজন :=সর্বাধিক_ওজন, w

• ফলাফল:=অসীম

• যখন সর্বাধিক_ওজন>=0, করুন

  • d, ওজন :=bfs(0, max_weight)

  • যদি d>=0 হয়, তাহলে

    • ফলাফল :=ফলাফলের সর্বনিম্ন, d * ওজন

    • সর্বাধিক_ওজন :=ওজন - 1

  • অন্যথায়,

    • লুপটি বন্ধ করুন

• ফলাফল <অসীম অন্যথায় -1

  হলে ফলাফল ফেরত দিন

• একটি ফাংশন bfs() সংজ্ঞায়িত করুন। এটি রুট নেবে, weight_cap

  • লক্ষ্য :=N - 1

  • প্রশ্ন :=মূল, 0, 0

    ধারণকারী একটি ডিক

  • পরিদর্শন করা হয়েছে :=[মিথ্যা] * N

  • পরিদর্শন [0] :=সত্য

  • যখন Q খালি নয়, করুন

    • v, d, current_weight :=Q

      থেকে শেষ উপাদান মুছে দিন

    • যদি v একই হয় N - 1, তাহলে

      • রিটার্ন d, বর্তমান_ওজন

    • প্রতিটি w এর জন্য গ্রাফ[v], করুন

      • যদি পরিদর্শন করা হয় [w] অ-শূন্য হয়, তাহলে

        • পরবর্তী পুনরাবৃত্তি চালিয়ে যান

      • new_weight :=ওজন[v, w]

      • যদি নতুন_ওজন <=ওজন_ক্যাপ, তাহলে

        • পরিদর্শন [w] :=সত্য

        • Q

          এর বাম দিকে (w, d + 1, সর্বাধিক (বর্তমান_ওজন, নতুন_ওজন)) যোগ করুন

  • রিটার্ন -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
                     zQ.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