$\Huge\text{GPSDUEL Solution}$

----------

:::info
🔗 Links:
📌 Tags: `Graph`
✍ Writer: Hoàng Việt
📄 Content:
[TOC]
:::

---------

## Thuật toán

Gọi $dist[t, u]$ là độ dài đường đi ngắn nhất khi đi từ đỉnh $u$ đến đỉnh $n$ đối với máy GPS thứ $t$.

Tính mảng $dist$ bằng $Dijkstra$ trên hai đồ thị đối với hai máy GPS.

Khi đi từ đỉnh $X$ qua đỉnh $Y$ bằng một cạnh trực tiếp, máy GPS thứ $t$ sẽ phàn nàn khi $dist[t, X] < dist[t, Y] + cost(X, Y)$ với $cost(X, Y)$ là trọng số của cạnh $(X, Y)$ đối với máy GPS thứ $t$.

Tạo một đồ thị mới, giữ nguyên các cạnh cũ nhưng thay đổi trọng số

Trọng số của cạnh $(X, Y)$ là số lượng máy GPS sẽ phàn nàn khi đi từ đỉnh $X$ qua đỉnh $Y$.

Kết quả bài toán là độ dài đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $n$ trên đồ thị mới, tiếp tục sử dụng $Dijkstra$ để tính.

Độ phức tạp $O((n + m) * log(n))$.

------------

Tham khảo code mẫu ở [đây](https://ideone.com/BUs0rF).