Editorial for Xây dựng đồ thị

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

Subtask 1: Ta đơn giản xây dựng các cạnh với mỗi truy vấn và sử dụng các thuật toán tìm đường đi ngắn nhất, có thể sử dụng Floyd-Washall.

Độ phức tạp: $O(M.N^2 + N^3)$ ~O(M.N^2 + N^3)~

Subtask 2: Với điều kiện $R_i-L_i \le 3$ ~R_i-L_i \le 3~ $\forall$ ~\forall~ $1 \le i \le M$ ~1 \le i \le M~, số cạnh tối đa của đồ thị là $6M$ ~6M~. Tiến hành xây dựng các cạnh của đồ thị và sử dụng thuật toán Dijkstra kết hợp Hàng đợi ưu tiên để tìm kết quả.

Độ phức tạp: $O(N + M.log(N))$ ~O(N + M.log(N))~

Subtask 3: Thay vì xây dựng trực tiếp các cạnh của đồ thị, ta có thể tìm độ dài đường đi ngắn nhất từ đỉnh $1$ ~1~ đến các đỉnh khác như sau:

Sắp xếp các truy vấn theo thứ tự tăng dần giá trị $L_i$ ~L_i~.
Duyệt qua các truy vấn, với truy vấn thứ $i$ ~i~, tìm độ dài đường đi ngắn nhất từ đỉnh $1$ ~1~ đến đỉnh $L_i$ ~L_i~, ta gọi giá trị này là $d$ ~d~, sau đó tiến hành cập nhật độ dài đường đi ngắn nhất của các đỉnh $u$ ~u~ ( $L_i \le u \le R_i$ ~L_i \le u \le R_i~) với giá trị $d + C_i$ ~d + C_i~.
Bài toán trở thành việc truy vấn giá trị tại một vị trí và cập nhật giá trị trên một đoạn các vị trí liên tiếp. Có thể sử dụng cấu trúc dữ liệu Segment Tree để giải quyết.

Độ phức tạp: $O(N.log(N) + M.log(M) + M.log(N))$ ~O(N.log(N) + M.log(M) + M.log(N))~

Subtask 4: Ta không thể xây dựng cây truy vấn cho tối đa $10^9$ ~10^9~ vị trí. Thay vào đó, ta chỉ cần quan tâm đến các đỉnh $L_i$ ~L_i~, $R_i$ ~R_i~ của các truy vấn, hai đỉnh $1$ ~1~ và $N$ ~N~, tạm gọi là các đỉnh quan trọng. Tiến hành lưu và sắp xếp các đỉnh quan trọng. Với mỗi truy vấn, sử dụng tìm kiếm nhị phân để xác định các vị trí cần truy vấn và cập nhật.

Độ phức tạp: $O(M.log(M))$ ~O(M.log(M))~

Editorial for Xây dựng đồ thị

Comments