Vượt Lưới Tốn Ít Năng Lượng

Buổi 19 — Đường đi ngắn nhất
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một bảng lưới kích thước $R \times C$. Mỗi ô $(i, j)$ có một giá trị năng lượng tiêu tốn $A_{i, j} \ge 0$. Bạn xuất phát từ ô $(1, 1)$ và muốn đi đến ô $(R, C)$. Ở mỗi bước, bạn có thể di chuyển sang một trong 4 ô kề cạnh (trên, dưới, trái, phải). Tổng năng lượng của đường đi là tổng giá trị của tất cả các ô bạn đi qua (tính cả ô $(1, 1)$ và $(R, C)$). Hãy tìm tổng năng lượng nhỏ nhất có thể.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $R$ và $C$ ($1 \le R, C \le 500$).
  • $R$ dòng tiếp theo, mỗi dòng chứa $C$ số nguyên $A_{i, j}$ ($0 \le A_{i, j} \le 10^9$).
Dữ liệu ra
  • In ra tổng năng lượng nhỏ nhất để đi từ $(1, 1)$ đến $(R, C)$.
Ví dụ
Input Output
3 3\n1 3 1\n1 5 1\n4 2 1 7
2 3\n5 1 2\n1 1 5 12
Giới hạn
  • $1 \le R, C \le 500$
  • $0 \le A_{i, j} \le 10^9$
Draft saved