Hướng dẫn giải của Vé Tham Quan

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: Vé Tham Quan

Hướng tiếp cận

Bài toán yêu cầu tìm chi phí tối thiểu từ mỗi trạm $i$ để phủ được cả trạm $1$ và trạm $N$ . Ta mô hình bài toán dưới dạng đường đi ngắn nhất (shortest path) trên một đồ thị mở rộng.

Nhận xét quan trọng

Mô hình đồ thị mở rộng: Tạo đồ thị với $N + K$ đỉnh: $N$ đỉnh cho các trạm và $K$ đỉnh cho các vé. Đỉnh-vé $t$ kết nối với tất cả đỉnh-trạm trong đoạn $[a_{t}, b_{t}]$ bằng cạnh chi phí $0$ (khi đã "kích hoạt" vé, ta đi vào các trạm miễn phí). Cạnh từ đỉnh-trạm $c_{t}$ đến đỉnh-vé $t$ có chi phí $p_{t}$ (mua vé).
Dijkstra ba pha: Thay vì tìm đường đi ngắn nhất riêng lẻ cho mỗi trạm, ta chạy ba lần Dijkstra:
- Pha 1: Tính khoảng cách ngắn nhất từ trạm $1$ đến mọi đỉnh.
- Pha 2: Tính khoảng cách ngắn nhất từ trạm $N$ đến mọi đỉnh.
- Pha 3: Kết hợp: với mỗi đỉnh, khởi tạo $d i s t [v] = d i s t_l e f t [v] + d i s t_r i g h t [v]$ , rồi chạy Dijkstra một lần nữa để tính chi phí tối thiểu cho mỗi trạm xuất phát.
Segment tree để xử lý interval: Mỗi vé phủ một đoạn $[a_{i}, b_{i}]$ . Khi xử lý một trạm trong Dijkstra, ta cần tìm tất cả các vé có đoạn chứa trạm đó. Dùng segment tree lưu các vé theo đoạn, và xóa vé sau khi xử lý (mỗi vé chỉ được xử lý đúng một lần).

Thuật toán

Bước 1: Đọc input và sắp xếp vé

Sắp xếp các vé theo $a_{i}$ (đầu trái của đoạn).

Bước 2: Dijkstra với Segment Tree

Hàm dijkstra(dist):

Khởi tạo segment tree lưu giá trị $b_{i}$ (đầu phải) của các vé, sắp xếp theo $a_{i}$ .
Với mỗi đỉnh-trạm u lấy từ priority queue:
- Dùng segment tree tìm tất cả vé $t$ mà $a_{t} \leq u \leq b_{t}$ (tức là vé phủ trạm $u$ ).
- Xóa các vé đã tìm được khỏi segment tree.
- Cập nhật: nếu đỉnh-vé $t$ chưa được thăm tốt hơn, cập nhật chi phí và thêm $c_{t}$ vào priority queue với chi phí $d i s t [u] + p_{t}$ .

Bước 3: Ba pha Dijkstra

Pha 1: $d i s t_l e f t [0] = 0$ , chạy Dijkstra.
Pha 2: $d i s t_r i g h t [N - 1] = 0$ , chạy Dijkstra.
Pha 3: $d i s t [v] = d i s t_l e f t [v] + d i s t_r i g h t [v]$ , chạy Dijkstra.

Bước 4: Xuất kết quả

Với mỗi trạm $i$ , nếu $d i s t [i] < \infty$ thì in $d i s t [i]$ , ngược lại in $- 1$ .

Độ phức tạp

Thời gian: $O ((N + K) \log K)$ — mỗi vé được xử lý đúng một lần trong segment tree, Dijkstra chạy 3 lần.
Bộ nhớ: $O (N + K)$

Bình luận

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