Giả sử chúng ta phải lên kế hoạch cho một chuyến đi đường bộ bao gồm việc đến thăm các thành phố khác nhau từ các quốc gia khác nhau. Chúng tôi có một danh sách các đường 'R', trong đó mỗi phần tử được mô tả là (x, y, chi phí). x biểu thị thành phố bắt đầu của con đường, y biểu thị thành phố đích của con đường và chi phí biểu thị chi phí đi lại trên con đường đó. Chúng tôi cũng có một danh sách 'C' trong đó mỗi phần tử là một quốc gia và một phần tử chứa các thành phố của quốc gia đó. Bây giờ, chúng tôi cũng có thành phố xuất phát và thành phố đích là 'e', và chúng tôi muốn đi đến thành phố đích từ thành phố nguồn. Với tất cả thông tin này, chúng tôi phải tìm ra số lượng chuyến đi xuyên quốc gia tối thiểu mà chúng tôi phải thực hiện để hoàn thành chuyến đi và cả tổng chi phí đi lại cho chuyến đi. Chúng tôi phải in hai giá trị này dưới dạng đầu ra.
Vì vậy, nếu đầu vào giống như R =[[0, 1, 2], [1, 2, 2], [0, 2, 3], [1, 3, 3]], C =[[0], [1], [2, 3]], s =0, e =3, thì đầu ra sẽ là (2,5).
Vì vậy, để đi từ 0 đến 3, chúng ta đi theo con đường 0-> 1-> 3. Các con đường được thực hiện trên con đường này là [0, 1, 2] và [1, 3, 3]. Như vậy, tổng chi phí du lịch giữa các quốc gia là 2 và tổng chi phí là 2 + 3 =5.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- cont:=một bản đồ mới trong đó các giá trị mặc định là 0
- đối với mỗi idx chỉ mục và mục phần tử trong C, hãy thực hiện
- đối với mỗi k trong mục, thực hiện
- cont [k]:=idx
- đối với mỗi k trong mục, thực hiện
- adj_list:=một bản đồ mới chứa các danh sách dưới dạng các giá trị
- với mỗi a, b, wt trong R, thực hiện
- nếu cont [a] không giống với cont [b], thì
- wt:=wt + 10 ^ 10
- chèn một cặp (b, wt) vào cuối adj_list [a]
- nếu cont [a] không giống với cont [b], thì
- khoảng cách:=một bản đồ mới trong đó các giá trị mặc định là 10 ^ 20
- khoảng cách [s]:=0
- đã thăm:=một tập hợp mới
- t:=một heap mới chứa một cặp (0, s)
- trong khi t không trống, thực hiện
- cặp (d, c):=bật mục nhỏ nhất khỏi đống
- nếu c có trong đã thăm, thì
- chuyển sang lần lặp tiếp theo
- thêm c vào đã thăm
- đối với mỗi j, wt trong adj_list [c], thực hiện
- nếu khoảng cách [j]> d + wt, thì
- khoảng cách [j]:=d + wt
- chèn cặp (d + wt, j) vào đống t
- nếu khoảng cách [j]> d + wt, thì
- cặp trả về (giá trị sàn của (khoảng cách [e] / 10 ^ 10), (khoảng cách [e] mod 10 ^ 10))
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầ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)