Vé Tham Quan

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

1. 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é).

2. 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 $dist[v]=dist\_left[v]+dist\_right[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.

3. 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\le u\le 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í $dist[u]+p_t$.

Bước 3: Ba pha Dijkstra

• Pha 1: $dist\_left[0]=0$, chạy Dijkstra.
• Pha 2: $dist\_right[N-1]=0$, chạy Dijkstra.
• Pha 3: $dist[v]=dist\_left[v]+dist\_right[v]$, chạy Dijkstra.

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

Với mỗi trạm $i$, nếu $dist[i]<\infty$ thì in $dist[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)$