Hành Trình Người Sói

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

1. 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=tmodT$ là pha trăng. Vì $w_i\ge 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.

2. Đồ 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)modT)$ với trọng số $w$.

3. Thao tác "chờ" tạo cạnh trọng số 1 từ $(u,p)$ đến $(u,(p+1)modT)$ với mọi $u$ và $p$.

4. 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

1. Xây đồ thị mở rộng (không cần tường minh - xử lý khi duyệt):

   • Đỉnh: $(u,p)$ với $1\le u\le N$ và $0\le 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)modT)$ trọng số $w$
   • Cạnh chờ: $(u,p)\to (u,(p+1)modT)$ trọng số $1$

2. 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ờ

3. Kết quả: ${min}_{0\le p<T}\text{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\le r$: $l\le p\le r$
• Nếu $l>r$: $p\ge l$ hoặc $p\le r$

Độ phức tạp

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