Editorial for Đường đi ngắn nhất

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Với điều kiện $M \le N+10$ ~M \le N+10~, ta có thể xem đồ thị đã cho là một cây gồm $N-1$ ~N-1~ cạnh và có thêm tối đa $11$ ~11~ cạnh giữa các đỉnh.

Gọi $11$ ~11~ cạnh này là các cạnh đặc biệt, và các đỉnh tương ứng là các đỉnh đặc biệt. Đồ thị có tối đa $K=22$ ~K=22~ đỉnh đặc biệt.

Với mỗi truy vấn cần tìm độ dài đường đi ngắn nhất giữa hai đỉnh $u$ ~u~ và $v$ ~v~, đáp án truy vấn là đường đi ngắn nhất trong hai cách:

Đỉnh $u$ ~u~ có thể đến đỉnh $v$ ~v~ chỉ thông qua các cạnh của cây.
Đỉnh $u$ ~u~ đến một đỉnh $x$ ~x~ là đỉnh đặc biệt thông qua các cạnh của cây, từ đỉnh $x$ ~x~ đến một đỉnh đặc biệt $y$ ~y~ $(y \neq x)$ ~(y \neq x)~ thông qua các cạnh của cây và các cạnh đặc biệt, từ đỉnh $y$ ~y~ đến đỉnh $v$ ~v~ thông qua các cạnh của cây.

Khi đó, có tối đa $K^2$ ~K^2~ cặp đỉnh $(x,y)$ ~(x,y)~, ta có thể tính toán trước độ dài đường đi ngắn nhất giữa các cặp $(x,y)$ ~(x,y)~ thông qua $BFS$ ~BFS~.

Độ phức tạp: $O(NlogN + K(N+M) + QK^2logN)$ ~O(NlogN + K(N+M) + QK^2logN)~

Editorial for Đường đi ngắn nhất

Comments