Hướng dẫn giải của Chặn Đường (Gold)

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Chặn Đường (Gold)

Hướng tiếp cận

Bài toán yêu cầu tìm một cạnh để nhân đôi độ dài sao cho đường đi ngắn nhất từ $1$ đến $N$ tăng nhiều nhất.

Nhận xét quan trọng

Nếu cạnh được nhân đôi không nằm trên đường đi ngắn nhất hiện tại, thì đường đi ngắn nhất không thay đổi (vì đường cũ vẫn có thể dùng).
Do đó, ta chỉ cần xét các cạnh nằm trên đường đi ngắn nhất từ $1$ đến $N$ .
Một cạnh $(u, v, L)$ nằm trên đường đi ngắn nhất nếu: $d i s t_{1} [u] + L + d i s t_{N} [v] = d$ hoặc $d i s t_{1} [v] + L + d i s t_{N} [u] = d$ , trong đó $d$ là khoảng cách ngắn nhất ban đầu.

Thuật toán

Chạy Dijkstra từ đỉnh $1$ để tính $d i s t_{1} [i]$ — khoảng cách ngắn nhất từ $1$ đến mọi đỉnh.
Chạy Dijkstra từ đỉnh $N$ để tính $d i s t_{N} [i]$ — khoảng cách ngắn nhất từ $N$ đến mọi đỉnh.
Khoảng cách ngắn nhất ban đầu: $d = d i s t_{1} [N]$ .
Với mỗi cạnh (u,v,L) nằm trên đường đi ngắn nhất:
- Thêm $L$ vào độ dài cạnh đó (vì nhân đôi = tăng thêm $L$ ), tạm thời chạy Dijkstra lại từ $1$ đến $N$ .
- Hoặc: dùng phương pháp không chạy Dijkstra lại — xét tất cả đường đi thay thế qua các cạnh khác trong $O (M)$ sau khi đã có $d i s t_{1}$ và $d i s t_{N}$ .
Thực tế với $N \leq 250$ , $M \leq 25000$ : chạy Dijkstra $O (M \log N)$ cho từng cạnh trên đường đi ngắn nhất (tối đa $N - 1$ cạnh) vẫn đủ nhanh — tổng $O (N \cdot M \log N)$ .
Đáp án là $max (khoảng cách mới - d)$ trên tất cả các cạnh đã thử.

Độ phức tạp

Thời gian: $O (N \cdot M \log N)$ (có thể tối ưu thành $O (M \log N + N \cdot M)$ bằng cách không chạy lại Dijkstra hoàn toàn)
Bộ nhớ: $O (N + M)$

Bình luận

Không có bình luận tại thời điểm này.