Chương trình tìm số lần chuyển quốc gia tối thiểu và chi phí hành trình Python

Cho danh sách đường R (mỗi phần tử [x, y, cost]), danh sách quốc gia C (mỗi phần tử là danh sách thành phố của quốc gia đó), thành phố xuất phát s và đích e. Tìm số lần chuyển quốc gia tối thiểu và tổng chi phí tương ứng.

Ví dụ: R=[[0,1,2],[1,2,2],[0,2,3],[1,3,3]], C=[[0],[1],[2,3]], s=0, e=3 → (2, 5) (đường 0→1→3).

Giải thuật (Dijkstra biến đổi)

1. Ánh xạ mỗi thành phố đến chỉ số quốc gia
2. Xây đồ thị kề, tăng trọng số 10^10 cho cạnh liên quốc gia
3. Chạy Dijkstra tìm đường ngắn nhất
4. Số lần chuyển quốc gia = distance // 10^10, chi phí = distance % 10^10

Ví dụ triển khai

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()
    heap = [(0, s)]
    
    while heap:
        d, c = heappop(heap)
        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(heap, (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))

Đầu vào

[[0,1,2],[1,2,2],[0,2,3],[1,3,3]], [[0],[1],[2,3]], 0, 3

Đầu ra

(2, 5)