Lưới dịch chuyển tức thời

Buổi 22 — DP 2D & LIS Dynamic Programming Graphs
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$.

Draft saved