**CÁI NHÌN ĐẦU TIÊN**
Dễ thấy cách đồ thị hóa mỗi quận thành một đỉnh, mỗi vé thành một hay nhiều cạnh có hướng và giá vé thành trọng số của các cạnh đó. Bài toán được đưa về tìm đường đi có trọng số nhỏ nhất từ một đỉnh đến mọi đỉnh còn lại của đồ thị, thường được giải bằng thuật toán [Dijkstra](https://viblo.asia/p/thuat-toan-dijkstra-va-ung-dung-aWj53zgQl6m). Nhưng như đã nói, mỗi vé có thể đồ thị hóa thành nhiều cạnh nên trong trường hợp xấu nhất, đồ thị sẽ có $n \cdot q$ cạnh và với $n, q \le 10^5$ thì có thể bị TLE.
Do đó, ta cần cách thêm nhiều cạnh hiệu quả trước khi thực hiện Dijkstra.
**Ý TƯỞNG 1**
Ta thấy việc thêm nhiều cạnh chỉ xảy ra với vé loại 2, 3. Dù số cạnh có thể lên đến $n$, một trong hai đầu mút của các cạnh này nằm hoàn toàn trong một phân đoạn $\[l, r\]$.
$\implies$ Thay vì nghĩ "thêm mọi cạnh $uv$ (hay $vu$) với $v$ thuộc $\[l, r\]$", hãy nghĩ "thêm một cạnh từ $u$ đến $\[l, r\]$ (hay ngược lại)".
$\implies$ Mạnh hơn nữa, một đỉnh $u$ cũng có thể được coi như một phân đoạn $\[u, u\]$ để đồng nhất đối tượng phân đoạn ở hai đầu mút của ý tưởng thêm cạnh này.
Một cách tổng quát, ta đưa về bài toán thêm cạnh từ phân đoạn $\[x, y\]$ này đến phân đoạn $\[z, t\]$ kia.
**Ý TƯỞNG 2**
Hẳn bạn đọc đã nghĩ đến việc dùng cây phân đoạn ([segment tree](https://wiki.vnoi.info/algo/data-structures/segment-tree-extend)) để chia mỗi đoạn $\[x, y\]$, $\[z, t\]$ thành $\log n$ các đoạn nhỏ hơn do các node của cây phân đoạn quản lí và thêm cạnh trong $O(\log^2 n)$. Ý tưởng đó đúng và ta cần lưu ý các điều sau:
(1) Mọi node con của các node được chia ra từ đoạn $\[x, y\]$ cũng vào được các cạnh đã thêm. Do đó, "cây" phân đoạn xử lí đoạn $\[x, y\]$ phải có hướng từ con lên cha.
(2) Tương tự, nếu một cạnh đã thêm ra ở một node được chia ra từ đoạn $\[z, t\]$ thì cũng đến được mọi node con của node đó. Vì thế, "cây" phân đoạn xử lí đoạn $\[z, t\]$ phải có hướng *từ cha* xuống con.
Điều này cho thấy ta phải dựng 2 cây phân đoạn ngược chiều nhau, lần lượt là "cây lên" (1) và "cây xuống" (2).
Lưu ý cần thêm $n$ cạnh nữa giữa các node quản lí mỗi đoạn $\[u, u\]$ ở "cây xuống" với phiên bản của nó ở "cây lên" (2 node ở 2 cây cùng quản lí một đoạn thì hiển nhiên từ node "xuống" có thể tới chính đoạn đó ở node "lên", nhưng ta chỉ cần thêm các cạnh như vậy ở lá là đã đảm bảo tính đúng đắn của thuật toán).
Sau khi dựng xong 2 cây phân đoạn như trên, ta có thể thực hiện Dijkstra từ node "lên" quản lí đoạn $\[s, s\]$ và in kết quả ở các node "xuống" quản lí mỗi đoạn $\[u, u\]$.
**HƯỚNG ĐI TIẾP**
Nếu trọng số cạnh không là hằng số $w$ mà là bậc thang thì cách dựng cây phân đoạn sẽ thay đổi như thế nào? (chẳng hạn như $w(u, v) = v - l + 1$, xem thêm bài [TRANSPORT](https://marisaoj.com/problem/707)).
sasaki2c
Created at
4 likes