Tổng quan

Bài toán này có phát biểu khá giống thuật toán Dijsktra nổi tiếng. Và một điều thú vị là nếu các bạn áp dụng thuật toán đó vào bài này (đồng thời thay các phép toán \(+\) thành \(|\)) thì sẽ đạt được khá nhiều điểm (\(76/100\)). Các bạn cũng có thể áp dụng những thuật đường đi ngắn nhất khác như Bellman-Ford. Mặc dù các thuật này không giải quyết hoàn toàn bài toán, chúng có thể giúp các bạn kiếm được kha khá điểm trên những đồ thị ngẫu nhiên.

Lời giải

Lời giải bài toán này chỉ sử dụng các thuật đồ thị cơ bản BFS/DFS.

Để ý rằng chúng ta đang làm việc trên phép tính \(OR\), là một phép tính trên bit nhị phân. Ý tưởng tự nhiên là biểu diễn tất cả các giá trị cạnh theo hệ nhị phân rồi giải bài toán với từng bit riêng biệt.

Để tìm con đường ngắn nhất, ta sẽ tham lam từ các bit lớn đến nhỏ (bit thứ \(30\) về bit \(0\)). Với bit thứ \(i\), chúng ta sẽ kiểm tra xem liệu đáp số có bắt buộc phải chứa bit này không, nói cách khác, bit thứ \(i\) trong đáp số có bắt buộc phải bằng 1 hay không?

Việc kiểm tra rất đơn giản. Gọi \(G\) là đồ thị con của đồ thị hiện tại, đồng thời \(G\) chỉ chứa các cạnh không chứa bit \(i\) trong biểu diễn nhị phân. Chúng ta sẽ dfs từ \(a\) và xem thử \(b\) có được thăm hay không.

Tại đây chúng ta có hai trường hợp:

1. \(b\) không được thăm. Tức là bit thứ \(i\) bắt buộc phải bằng \(1\). Do đó các cạnh có bit \(i\) bằng \(1\) có thể được dùng cho những bit sau. Cộng thêm \(2^i\) vào đáp số.

2. \(b\) được thăm. Tức là có đường đi mà bit \(i\) bằng \(0\). Tất nhiên chúng ta sẽ ưu tiên đường đi này. Để phòng trừ hậu họa, chúng ta sẽ xóa hết những cạnh mà \(bit\) thứ \(i\) bằng \(1\).

Để ý rằng, việc kiểm tra có in ra \(-1\) hay không chính là bước kiểm tra bit \(30\).

Độ phức tạp

\(O((n + m)\log{MAX_E})\), với \(MAX_E\) ở đây là giá trị lớn nhất của một cạnh.