Hướng dẫn giải của Hành Trình Người Sói

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

Hướng tiếp cận

Bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số phụ thuộc thời gian (time-dependent shortest path). Ta mở rộng không gian trạng thái bằng cách thêm chiều "pha trăng" và dùng Dijkstra trên đồ thị mở rộng.

Nhận xét quan trọng

Trạng thái đầy đủ của người sói là $(u, p)$ với $u$ là khu vực hiện tại và $p = t mod T$ là pha trăng. Vì $w_{i} \geq 1$ , hai trạng thái $(u, p)$ khác nhau hoàn toàn xác định khả năng di chuyển tiếp.
Đồ thị mở rộng có $N \times T$ đỉnh. Mỗi cạnh gốc $(u, v, w, l, r)$ tạo ra nhiều cạnh trong đồ thị mở rộng: với mỗi pha $p \in [l, r]$ , ta có cạnh từ $(u, p)$ đến $(v, (p + w) mod T)$ với trọng số $w$ .
Thao tác "chờ" tạo cạnh trọng số 1 từ $(u, p)$ đến $(u, (p + 1) mod T)$ với mọi $u$ và $p$ .
Khoảng pha $[l, r]$ có thể quay vòng (khi $l > r$ ), cần xử lý đúng.

Thuật toán

Time-Expanded Dijkstra

Xây đồ thị mở rộng (không cần tường minh - xử lý khi duyệt):
- Đỉnh: $(u, p)$ với $1 \leq u \leq N$ và $0 \leq p < T$
- Cạnh di chuyển: với mỗi cạnh gốc $(u, v, w, l, r)$ và pha $p$ hợp lệ (trong $[l, r]$ ), thêm cạnh $(u, p) \to (v, (p + w) mod T)$ trọng số $w$
- Cạnh chờ: $(u, p) \to (u, (p + 1) mod T)$ trọng số $1$
Dijkstra từ trạng thái $(1, 0)$ :
- dist[u][p] = thời gian ngắn nhất đến khu vực $u$ ở pha $p$
- Dùng priority queue min-heap
- Khi xét trạng thái $(u, p)$ , thử tất cả cạnh kề của $u$ và cạnh chờ
Kết quả: ${min}_{0 \leq p < T} dist [N] [p]$ . Nếu tất cả đều $\infty$ , in $- 1$ .

Kiểm tra pha hợp lệ

Pha $p$ thuộc khoảng $[l, r]$ :

Nếu $l \leq r$ : $l \leq p \leq r$
Nếu $l > r$ : $p \geq l$ hoặc $p \leq r$

Độ phức tạp

Thời gian: $O ((N \cdot T + M \cdot T) \log (N \cdot T))$ - Dijkstra trên đồ thị mở rộng với $N \cdot T$ đỉnh và $(M + N) \cdot T$ cạnh.
Bộ nhớ: $O (N \cdot T + M)$ - mảng khoảng cách và danh sách kề.

Bình luận

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