Lưới dịch chuyển tức thời
Đề bài
Cho một bảng lưới $N \times M$, mỗi ô $(i, j)$ có chi phí đi qua là $A_{i,j}$. Bạn xuất phát từ $(1, 1)$ và cần đến $(N, M)$ với tổng chi phí nhỏ nhất (tính cả $A_{1,1}$ và $A_{N,M}$). Ở mỗi bước, bạn có thể đi sang phải hoặc xuống dưới. Ngoài ra, có $K$ cổng dịch chuyển một chiều từ ô $(r_1, c_1)$ đến ô $(r_2, c_2)$ với chi phí kích hoạt $w$ (điều kiện $r_1 \le r_2, c_1 \le c_2$ và $(r_1, c_1) \neq (r_2, c_2)$). Khi sử dụng cổng dịch chuyển từ $(r_1, c_1)$ đến $(r_2, c_2)$, bạn trả thêm chi phí $w + A_{r_2, c_2}$ (vì phải bước vào ô đích).
Cấu trúc con tối ưu: vì mọi bước đi và cổng dịch chuyển đều không giảm tọa độ $(r, c)$, lưới tạo thành DAG theo thứ tự từ điển $(i, j)$.
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên $N, M, K$. $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên $A_{i,j}$. $K$ dòng tiếp theo, mỗi dòng chứa 5 số nguyên $r_1, c_1, r_2, c_2, w$.
Dữ liệu ra
Một số nguyên duy nhất là tổng chi phí nhỏ nhất từ $(1, 1)$ đến $(N, M)$.
Ví dụ
| Input | Output |
|---|---|
| 3 3 1 1 10 10 10 10 10 10 10 1 1 1 3 3 2 |
4 |
| 3 4 2 1 5 5 5 5 100 100 5 5 5 5 1 1 1 2 4 1 1 2 3 3 0 |
8 |
Giới hạn
$1 \le N, M \le 500$, $0 \le K \le 5000$, $0 \le A_{i,j}, w \le 10^9$.
Community Discussion