Tổng đường đi nhỏ nhất trong lưới

Mô tả bài toán

Thay vì đếm đường đi, bài này hỏi đường đi nào tốn ít chi phí nhất. Mỗi ô có một chi phí, và chi phí của cả đường đi là tổng chi phí các ô đã bước qua, kể cả ô xuất phát và ô đích. Bảng quy hoạch động hai chiều vì thế phải cộng thêm chi phí ô hiện tại sau khi chọn ô trước đó.

Yêu cầu

Cho lưới n hàng, m cột, mỗi ô ghi một số nguyên không âm. Đi từ ô góc trên bên trái tới ô góc dưới bên phải, mỗi bước chỉ được sang phải hoặc xuống dưới. Hãy tìm tổng chi phí nhỏ nhất, tính cả ô đầu và ô cuối.

Quy ước nộp bài

Nộp tệp solution.cpp đọc dữ liệu từ stdin và ghi kết quả ra stdout. Chỉ in một số nguyên trên một dòng, không kèm chữ hay dấu cách thừa.

Ràng buộc

• Chỉ đi sang phải hoặc xuống dưới, không đi chéo.
• Chi phí ô xuất phát và ô đích đều được tính.
• Thời gian cho mỗi bộ dữ liệu là 1 giây.