Hướng dẫn giải của Giao Hàng

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: Giao Hàng

Hướng tiếp cận

Xây dựng đồ thị lưới với các nút là vị trí tọa độ nguyên. Với mỗi chặng từ điểm $i$ đến điểm $i + 1$ , chạy Dijkstra trên lưới tránh các nút là điểm trung gian (không được đi qua). Tổng chi phí các chặng là đáp án.

Nhận xét quan trọng

Khoảng cách tối thiểu giữa hai điểm trên lưới không có chướng ngại vật là khoảng cách Manhattan. Nhưng vì đường đi không được qua các điểm khác, đôi khi phải đi vòng.
Không gian toạ độ lên đến $10^{6}$ , không thể xây đồ thị toàn bộ. Thay vào đó chỉ cần quan tâm đến tọa độ của $N$ điểm và 4 láng giềng của chúng để tạo đồ thị nén (compressed coordinate graph).
Mỗi chặng từ $i$ đến $i + 1$ phải tránh tất cả điểm khác (trừ $i$ và $i + 1$ ). Chạy Dijkstra riêng cho từng chặng.
Nếu không tồn tại đường đi hợp lệ cho một chặng nào đó, in $- 1$ .

Thuật toán

Thu thập tất cả tọa độ $x$ và $y$ của $N$ điểm, cùng với $x \pm 1$ , $y \pm 1$ để tạo lưới tọa độ rời rạc.
Xây đồ thị: mỗi nút là giao điểm $(c x_{i}, c y_{j})$ trong lưới nén, các cạnh nối hai nút kề nhau với trọng số bằng khoảng cách thực.
Với mỗi chặng (src,dst):
- Đánh dấu các điểm "cấm" (tất cả điểm ngoại trừ $s r c$ và $d s t$ ).
- Chạy Dijkstra từ $s r c$ đến $d s t$ trên đồ thị nén, bỏ qua các nút bị cấm.
- Cộng kết quả vào tổng.
In tổng hoặc $- 1$ nếu không thể.

Độ phức tạp

Thời gian: $O (N \cdot (N^{2} \log N))$ — mỗi chặng Dijkstra trên đồ thị $O (N^{2})$ nút
Bộ nhớ: $O (N^{2})$

Bình luận

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