পাইথনে রোড ট্রিপে ন্যূনতম আন্তর্জাতিক ভ্রমণ ও খরচ বের করা

বিভিন্ন দেশের সিটি গুলোর মাধ্যমে রোড ট্রিপে ন্যূনতম দেশান্তরগত যাত্রা এবং মোট খরচ বের করা হয়। প্রতিটি রোডের কস্ট এবং দেশের সিটি ম্যাপ দেওয়া থাকে।

ইনপুট উদাহরণ

R = [[0,1,2], [1,2,2], [0,2,3], [1,3,3]]
C = [[0], [1], [2,3]]
s = 0, e = 3

আউটপুট: (2, 5) (২টি দেশান্তরগত যাত্রা, খরচ ৫)

অ্যালগরিদম

প্রতিটি সিটির দেশ আইডি ম্যাপ করুন।
অ্যাডজেসেন্সি লিস্টে এজ ওয়েট সেট করুন: একই দেশের মধ্যে কস্ট = আসল কস্ট, আলাদা দেশ হলে কস্ট + ১০¹⁰।
ডায়েকস্ট্রা অ্যালগরিদম চালিয়ে শর্টেস্ট পথ বের করুন।
ফাইনাল ডিস্ট্যান্স থেকে দেশান্তরগত যাত্রা = dist // 10**10, খরচ = dist % 10**10।

পাইথন কোড

from collections import defaultdict
from heapq import heappush, heappop

def solve(R, C, s, e):
    cont = defaultdict(int)
    for idx, item in enumerate(C):
        for k in item:
            cont[k] = idx

    adj_list = defaultdict(list)
    for a, b, wt in R:
        if cont[a] != cont[b]:
            wt += 10**10
        adj_list[a].append((b, wt))

    distance = defaultdict(lambda: 10**20)
    distance[s] = 0
    visited = set()
    t = [(0, s)]

    while t:
        d, c = heappop(t)
        if c in visited:
            continue
        visited.add(c)
        for j, wt in adj_list[c]:
            if distance[j] > d + wt:
                distance[j] = d + wt
                heappush(t, (d + wt, j))

    return distance[e] // 10**10, distance[e] % 10**10

# টেস্ট
print(solve([[0,1,2],[1,2,2],[0,2,3],[1,3,3]], [[0],[1],[2,3]], 0, 3))  # (2, 5)

ব্যাখ্যা

বড় পেনাল্টি (১০¹⁰) যোগ করে দেশান্তরগত যাত্রা মিনিমাইজ করা হয়েছে। ডায়েকস্ট্রা নিশ্চিত করে সর্বনিম্ন টোটাল কস্ট (পেনাল্টি + আসল কস্ট)।