Giả sử cho một đồ thị vô hướng có trọng số, cần tìm đường đi có phạt tối thiểu từ đỉnh a đến đỉnh b. Phạt của một đường là phép OR bitwise của trọng số tất cả các cạnh trên đường. Ta phải tìm đường "phạt tối thiểu" này, trả về -1 nếu không có đường.
Ví dụ, với đầu vào như hình minh họa, start (s) = 1, end (e) = 3, đầu ra sẽ là 15.
Có hai đường giữa đỉnh 1 và 3. Đường tối ưu là 1→2→3, phạt = (10 OR 5) = 15.
Giải pháp
Để giải quyết bài toán này, ta thực hiện các bước sau:
- Định nghĩa hàm helper(G, s, e):
- v := tập hợp mới
- c := danh sách kích thước n khởi tạo giá trị infinity
- heap := heap mới chứa cặp (0, s)
- Khi kích thước heap > 0:
- cst, cur := pop phần tử nhỏ nhất từ heap
- c[cur] := min(cst, c[cur])
- Nếu (cst, cur) trong v: tiếp tục
- Nếu cur == e: trả về c[cur]
- Thêm (cst, cur) vào v
- Với mỗi neighbor, n_cost trong G[cur]:
- Push ((n_cost OR cst), neighbor) vào heap
- Trả về c[e]
- G := danh sách n+1 danh sách rỗng
- Với mỗi item trong edges:
- u := item[0], v := item[1], w := item[2]
- Thêm (v, w) vào G[u], thêm (u, w) vào G[v]
- ans := helper(G, s, e)
- Trả về -1 nếu ans == inf, ngược lại trả về ans
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
import heapq
from math import inf
def helper(G, s, e):
v = set()
c = [inf] * len(G)
heap = [(0, s)]
while len(heap) > 0:
cst, cur = heapq.heappop(heap)
c[cur] = min(cst, c[cur])
if (cst, cur) in v:
continue
if cur == e:
return c[cur]
v.add((cst, cur))
for neighbor, n_cost in G[cur]:
heapq.heappush(heap, (n_cost | cst, neighbor))
return c[e]
def solve(n, edges, s, e):
G = [[] for _ in range(n + 1)]
for item in edges:
u, v, w = map(int, item)
G[u].append((v, w))
G[v].append((u, w))
ans = helper(G, s, e)
return -1 if ans == inf else ans
print(solve(4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)], 1, 3))
Đầu vào
4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)], 1, 3
Đầu ra
15