Giả sử có n thành phố được kết nối bởi hai loại đường: cao tốc và đường tắt. Chỉ có đường cao tốc được hiển thị trên bản đồ, tất cả đường tắt đều vắng mặt. Bộ phận giao thông muốn khai thác vận tải kết nối các thành phố sử dụng cả cao tốc và đường tắt. Ta biết có đường tắt giữa hai thành phố khi không có đường cao tốc nối chúng. Nhiệm vụ là tìm khoảng cách tối thiểu theo đường tắt từ một thành phố xuất phát đến tất cả các thành phố khác.
Ví dụ, với đầu vào như hình minh họa và đỉnh xuất phát s = 1, đầu ra sẽ là 3 1 2.
Nếu chỉ đi đường tắt, đường đi giữa thành phố 1 và 2 là 1→3→4→2, chi phí là 3.
Tương tự:
- 1 và 3: 1→3, chi phí 1.
- 1 và 4: 1→3→4, chi phí 2.
Giải pháp
Để giải quyết bài toán này, ta thực hiện các bước sau:
- graph := danh sách mới chứa n tập hợp (sets)
- Với mỗi cặp (x, y) trong edges:
- x := x - 1
- y := y - 1
- Thêm y vào graph[x]
- Thêm x vào graph[y]
- temp_arr := mảng mới kích thước n chứa giá trị -1
- b_set := map mới chứa khóa s - 1
- f := tập hợp mới chứa hiệu giữa các số 0 đến n và b_set
- index := 0
- Khi kích thước b_set > 0:
- Với mỗi phần tử a trong b_set:
- temp_arr[a] := index
- nxt := map mới chứa các giá trị của graph không phải tập con của b_set
- f := hiệu của f và nxt
- b_set := nxt
- index := index + 1
- Với mỗi phần tử a trong b_set:
- Trả về các giá trị khác 0 của temp_arr
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
def solve(n, edges, s):
graph = [set() for i in range(n)]
for (x, y) in edges:
x -= 1
y -= 1
graph[x].add(y)
graph[y].add(x)
temp_arr = [-1] * n
b_set = {s - 1}
f = set(range(n)).difference(b_set)
index = 0
while len(b_set) > 0:
for a in b_set:
temp_arr[a] = index
nxt = {f for f in f if not b_set.issubset(graph[f])}
f = f.difference(nxt)
b_set = nxt
index += 1
return (' '.join(str(t) for t in temp_arr if t > 0))
print(solve(4, [(1, 2), (2, 3), (1, 4)], 1))
Đầu vào
4, [(1, 2), (2, 3), (1, 4)], 1
Đầu ra
3 1 2