Giao Hàng

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

1. 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.
2. 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).
3. 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.
4. 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

1. 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.
2. 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.
3. 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ừ $src$ và $dst$).
   • Chạy Dijkstra từ $src$ đến $dst$ trên đồ thị nén, bỏ qua các nút bị cấm.
   • Cộng kết quả vào tổng.
4. In tổng hoặc $-1$ nếu không thể.

Độ phức tạp

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