পাইথনে প্রথম থেকে শেষ নোড পর্যন্ত রেস্ট্রিক্টেড পথের সংখ্যা বের করার প্রোগ্রাম

মনে করুন একটি অনডায়রিক্টেড ওজনযুক্ত সংযুক্ত গ্রাফ আছে। গ্রাফে n নোড আছে যারা ১ থেকে n পর্যন্ত লেবেল করা। একটি পথ start থেকে end হলো নোডের একটি সিকোয়েন্স [z0, z1, z2, ..., zk] যেখানে z0 হলো শুরুর নোড এবং zk হলো শেষ নোড এবং 0 <= i <= k-1 এর জন্য zi এবং zi+1-এর মধ্যএ একটি এজ থাকে। একটি পথের দূরত্ব হলো পথে ব্যবহৃত এজগুলোর ওজন যোগফল। dist(x) বলতে নোড n এবং নোড x-এর মধ্যবর্তী শর্টেস্ট দূরত্ব বোঝায়। একটি রেস্ট্রিক্টেড পথ হলো একটি বিশেষ পথ যা এছাড়াও dist(zi) > dist(zi+1) শর্তটি পূরণ করে যেখানে 0 <= i <= k-1। তাহলে নোড ১ থেকে নোড n পর্যন্ত রেস্ট্রিক্টেড পথের সংখ্যা বের করতে হবে। উত্তর বড় হলে 10^9 + 7 দিয়ে মডুলো রিটার্ন করুন।

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

আউটপুট হবে ৩ কারণ তিনটি রেস্ট্রিক্টেড পথ আছে: (1,2,5), (1,2,3,5), (1,3,5)।

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

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

graph := দেওয়া এজ লিস্ট থেকে বানানো অ্যাডজেসেন্সি লিস্ট
paths := 0 দিয়ে (n+1) সাইজের একটি অ্যারে
paths[n] := 1
dists := -1 দিয়ে (n+1) সাইজের একটি অ্যারে
q := একটি কিউ, এবং (0, n) ইনিশিয়ালি ইনসার্ট করুন
যখন q খালি না, तब
- (dist, node) := q-এর ফ্রন্ট এলিমেন্ট পপ করুন
- যদি dists[node] != -1 হয়, তবে
  - নেক্সট ইটারেশনে যান
- dists[node] := dist
- graph[node]-এ থাকা প্রতিটি অ্যাডজেসেন্ট নোড v এবং ওজন w-এর জন্য
  - যদি dists[v] == -1 হয়, তবে
    - (dist + w, v) কে q-এ ইনসার্ট করুন
  - অন্যথায় যখন dists[v] < dists[node] হয়, তবে
    - paths[node] := paths[node] + paths[v]
- যদি node == 1 হয়, তবে
  - paths[node] mod 10^9+7 রিটার্ন করুন
0 রিটার্ন করুন

উদাহরণ

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

from collections import defaultdict from heapq import heappop, heappush def solve(n, edges):    graph = defaultdict(dict)    for u, v, w in edges:       graph[u][v] = w       graph[v][u] = w    paths = [0] * (n+1)    paths[n] = 1    dists = [-1] * (n+1)    q = [(0, n)]    while q:       dist, node = heappop(q)       if dists[node] != -1:          continue       dists[node] = dist       for v, w in graph[node].items():          if dists[v] == -1:             heappush(q, (dist + w, v))          elif dists[v] < dists[node]:             paths[node] += paths[v]       if node == 1:          return paths[node] % (10**9 + 7) return 0 n = 5 edges = [(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5,1),(5,4,10)] print(solve(n, edges))

ইনপুট

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