ন্যূনতম শাস্তি (পাইথন)

ধরুন আমাদের একটি অনির্দেশিত, ওজনযুক্ত গ্রাফ দেওয়া হয়েছে এবং নোড এ থেকে নোড বি পর্যন্ত ন্যূনতম সম্ভাব্য শাস্তি সহ পথটি খুঁজে বের করতে বলা হয়েছে। একটি পথের শাস্তি হল পথের সমস্ত প্রান্তের ওজনের বিটওয়াইজ বা ওজন। সুতরাং, আমাদের অবশ্যই এমন একটি 'ন্যূনতম শাস্তি' পথ খুঁজে বের করতে হবে, এবং যদি দুটি নোডের মধ্যে কোনো পথ না থাকে, তাহলে আমরা -1 ফিরে আসব।

সুতরাং, যদি ইনপুট মত হয়

শুরু (গুলি) =1, শেষ (ই) =3; তাহলে আউটপুট হবে 15।

শীর্ষবিন্দু 1 এবং 3 এর মধ্যে দুটি পথ রয়েছে৷ সর্বোত্তম পথটি হল 1->2->3, পথটির মূল্য (10 বা 5) =15৷

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

একটি ফাংশন সাহায্যকারী() সংজ্ঞায়িত করুন। এতে G, s, e
- v :=একটি নতুন সেট
- c :=আকার n এর একটি নতুন তালিকা ইনফিনিটি মান সহ শুরু করা হয়েছে
- স্তূপ :=জোড়া (0, s) ধারণকারী একটি নতুন গাদা
- যখন স্তূপের আকার> 0, do
  - cst :=স্তূপ থেকে ক্ষুদ্রতম আইটেম পপ করুন
  - cur :=গাদা থেকে ক্ষুদ্রতম আইটেম পপ করুন
  - c[cur] :=সর্বনিম্ন (cst, c[cur])
  - যদি (cst, cur) v এ উপস্থিত থাকে, তাহলে
    - পরবর্তী পুনরাবৃত্তির জন্য যান
  - যদি cur হয় e এর মত, তাহলে
    - রিটার্ন c[cur]
  - v-তে জোড়া (cst, cur) যোগ করুন
  - প্রতিটি প্রতিবেশীর জন্য, G[cur]-এ n_cost, do
    - মানগুলিকে (n_cost OR cst), প্রতিবেশী) হিপ করতে ঠেলে
- রিটার্ন c[e]
G :=[n + 1 ইমোটি তালিকা সহ একটি নতুন তালিকা]
প্রান্তে থাকা প্রতিটি আইটেমের জন্য, করুন
- u :=আইটেম[0]
- v :=আইটেম[1]
- w :=আইটেম[2]
- G[u] এর শেষে জোড়া (v, w) সন্নিবেশ করুন
- G[v] এর শেষে জোড়া (u, w) ঢোকান
উত্তর :=সাহায্যকারী (জি, এস, ই)
রিটার্ন -1 যদি উত্তরগুলি inf এর মত হয় অন্যথায় উত্তর দেয়

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

import heapq
from math import inf

def helper(G, s, e):
    v = set()
    c = [inf] * len(G)
    heap = [(0, s)]
    while len(heap) > 0:
        cst, cur = heapq.heappop(heap)
        c[cur] = min(cst, c[cur])
        if (cst, cur) in v:
            continue
        if cur == e:
            return c[cur]
        v.add((cst, cur))
        for neighbor, n_cost in G[cur]:
            heapq.heappush(heap, (n_cost | cst, neighbor))
    return c[e]

def solve(n, edges, s, e):
    G = [[] for _ in range(n + 1)]
    for item in edges:
        u, v, w = map(int, item)
        G[u].append((v, w))
        G[v].append((u, w))
    ans = helper(G, s, e)
    return -1 if ans == inf else ans

print(solve(4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)], 1, 3))

ইনপুট

4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)], 1, 3