পাইথনে সব চিঠি ডেলিভারি করার জন্য ন্যূনতম পথ বের করার প্রোগ্রাম

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

যেমন, ইনপুট এমন হলে

এবং ডেলিভারি করা শহরগুলো (delv) ১, ২, এবং ৪ হলে, আউটপুট হবে ৪।

কর্মী শহর ১, ২, অথবা ৪ থেকে শুরু করতে পারে। শহর ১ থেকে শুরু করলে পথ হবে 1→2→4, বিপরীতক্রমে শহর ৪ থেকে 4→2→1। মোট খরচ ১ + ৩ = ৪। শহর ২ থেকে শুরু করলে খরচ বেশি হবে।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

depth_search() ফাংশন ডিফাইন করুন। এটি node, p প্যারামিটার নেবে
- d1 := -infinity, d2 := -infinity
- adj_list[node]-এ থাকা প্রতিটি (x, y) জোড়ার জন্য
  - যদি x != p হয়, তবে
    - d1 := max(d1, depth_search(x, node) + y)
    - যদি d1 > d2 হয়, তবে
      - d2 এবং d1-এর মান স্ব্যাপ করুন
    - ti[node] := ti[node] + ti[x]
    - যদি 0 < ti[x] < k হয়, তবে
      - SUM := SUM + y
  - যদি d1 > 0 হয়, তবে
    - MAX := max(MAX, d1 + d2)
  - যদি d2 > 0 এবং tj[node] != 0 হয়, তবে
    - MAX := max(MAX, d2)
  - যদি tj[node] != 0 হয়, তবে
    - d2 := max(0, d2)
  - d2 রিটার্ন করুন
k := delv-এর সাইজ
adj_list := একটি খালি ম্যাপ
ti := 0 দিয়ে (nodes + 5) সাইজের একটি লিস্ট
tj := 0 দিয়ে (nodes + 5) সাইজের একটি লিস্ট
delv-এ থাকা প্রতিটি i-এর জন্য
- ti[i] := 1, tj[i] := 1
roads-এ থাকা প্রতিটি item-এর জন্য
- x := item[0], y := item[1], c := item[2]
- adj_list[x] এবং adj_list[y]-এ (y, c) এবং (x, c) অ্যাপেন্ড করুন
SUM := 0, MAX := 0
depth_search(1, 1) কল করুন
return SUM * 2 - MAX

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:

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