--- author: little tags: Sơ tán title: Sơ tán Solution --- $\Huge\text{Sơ tán Solution}$ ------- :::info 📌 Tags: `bfs` ✍️ Writer: little 📋 Content: [TOC] ::: ----- ## Thuật toán Trước hết hãy xem thử thuật toán trâu của bài này xem. Bởi vì mình cần biết là với mỗi đỉnh thì số bước đi tối thiểu để đi từ đỉnh này đến một lối thoát hiểm gần nhất là bao nhiêu. Thì cách trâu đơn giản chỉ là mình $for$ đỉnh hiện tại sau đó $bfs$ từ đỉnh đó ra toàn bộ đồ thị, đỉnh có lối thoát hiểm đầu tiên được thăm sẽ là kết quả. Nhưng với cách làm này thì độ phức tạp bài toán là $O(n ^ 2)$. Ta sẽ cải tiến nó bằng cách sử dụng kĩ thuật **bfs đa nguồn**. Ban đầu ta sẽ thêm các đỉnh có lối thoát hiểm cả $queue$ sau đó lần lượt loang ra các đỉnh lân cận. Gọi $res_u$ là khoảng cách ngắn nhất từ đỉnh $u$ đến đỉnh có lối thoát hiểm gần nhất. Khi duyệt đến đỉnh $u$ thì ta cập nhật $res_u = min(res_u, res_v + 1)$ với $v$ là đỉnh được thăm trước $u$ và kề với $u$. Cách này làm trong độ phức tạp $O(n)$ nhưng nó vẫn đảm bảo được tính đúng đắn. ---- Tham khảo code ở [đây](https://ideone.com/PPxAzt)