পাইথনে সমস্ত অক্ষর সরবরাহ করার সর্বনিম্ন পথ খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন n শহর আছে এবং যেগুলো n -1 রাস্তার সাথে সংযুক্ত। অন্য শহর থেকে একটি শহর পরিদর্শন করা যেতে পারে. এখন শহরগুলির ডাক ব্যবস্থা প্রতিদিন কে অক্ষর সরবরাহ করে। চিঠির গন্তব্য k বিভিন্ন শহর হতে পারে। একজন ডাককর্মীকে প্রতিদিন তাদের ঠিকানায় সমস্ত চিঠি পৌঁছে দিতে হয়। সমস্ত চিঠি সরবরাহ করার জন্য কর্মীকে ন্যূনতম কত দূরত্ব অতিক্রম করতে হবে তা আমাদের খুঁজে বের করতে হবে। কর্মী যে কোন শহর থেকে শুরু করতে পারেন।

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

এবং চিঠিগুলি শহরে (ডেলভ) 1, 2, এবং 4 বিতরণ করতে হবে; তাহলে আউটপুট হবে 4.

কর্মী 1, 2 বা 4 শহর থেকে ডেলিভারি শুরু করতে পারেন৷ যদি কর্মী শহর 1 থেকে শুরু করেন, তাহলে পথটি হবে 1->2->4, শহর 4 এর ক্ষেত্রে উল্টোটা; 4->2->1। মোট খরচ হবে 1 + 3 =4। যদি সে শহর 2 থেকে শুরু করে, তাহলে খরচটা অন্য দুটির চেয়ে বেশি হবে।

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

• একটি ফাংশন depth_search() সংজ্ঞায়িত করুন। এটি নোড, p
  নেবে
  • d1 :=-ইনফিনিটি
  • d2 :=-ইনফিনিটি
  • প্রতিটি জোড়ার জন্য x, y adj_list[নোড]-এ করুন
    • যদি x p এর মত না হয়, তাহলে
      • d1 :=সর্বাধিক (d1, depth_search(x, node) + y)
      • যদি d1> d2 হয়, তাহলে
        • d2 এবং d1-এর মান অদলবদল করুন
      • ti[নোড] :=ti[নোড] + ti[x]
      • যদি 0
      • SUM :=SUM + y
  • যদি d1> 0 হয়, তাহলে
    • MAX :=সর্বাধিক (MAX, d1 + d2)
  • যদি d2> 0 এবং tj[নোড] অ-শূন্য হয়, তাহলে
    • MAX :=সর্বাধিক (MAX, d2)
  • যদি tj[নোড] অ-শূন্য হয়, তাহলে
    • d2 :=সর্বোচ্চ(0, d2)
  • রিটার্ন d2

উদাহরণ

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

import sys
from math import inf as INF
sys.setrecursionlimit(10**5 + 5)

def depth_search(node, p):
    global SUM, MAX
    d1 = -INF
    d2 = -INF

    for x, y in adj_list[node]:
        if x != p:
            d1 = max(d1, depth_search(x, node) + y)
            if d1 > d2:
                d1, d2 = d2, d1

            ti[node] += ti[x]
            if 0 < ti[x] < k:
                SUM += y

    if d1 > 0: MAX = max(MAX, d1 + d2)
    if d2 > 0 and tj[node]: MAX = max(MAX, d2)
    if tj[node]: d2 = max(0, d2)

    return d2

def solve(nodes, delv, roads):
    global k, ti, tj, adj_list, SUM, MAX
    k = len(delv)
    adj_list = {}
    ti = [0] * (nodes + 5)
    tj = [0] * (nodes + 5)

    for i in delv:
        ti[i] = tj[i] = 1

    for item in roads:
        x, y, c = map(int, item)
        if x not in adj_list: adj_list[x] = []
        if y not in adj_list: adj_list[y] = []

        adj_list[x].append([y, c])
        adj_list[y].append([x, c])

    SUM = 0
    MAX = 0
    depth_search(1,1)
    return SUM * 2 - MAX

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

ইনপুট

5, [1, 2, 4], [(1,2,1),(2,3,2),(2,4,3),(1,5,1)]

আউটপুট

4