Elearning CodePath – CTP Online Judge

Chi phí trên lưới

DJK03

🟢 Easy #Shortest Path

## Đề bài

Cho một bảng gồm `R` hàng và `C` cột. Ô `(i, j)` có chi phí `a[i][j]`.

Bạn bắt đầu ở ô `(1, 1)` và muốn đi đến ô `(R, C)`. Từ một ô, bạn có thể đi sang một trong bốn ô kề cạnh: trên, dưới, trái, phải nếu ô đó còn nằm trong bảng.

Chi phí của một hành trình bằng tổng chi phí của tất cả các ô đã đi qua, bao gồm cả ô bắt đầu và ô kết thúc.

Hãy tìm chi phí nhỏ nhất để đi từ `(1, 1)` đến `(R, C)`.

## Dữ liệu vào

- Dòng đầu chứa hai số nguyên `R`, `C`.
- `R` dòng tiếp theo, mỗi dòng chứa `C` số nguyên, số thứ `j` ở dòng thứ `i` là `a[i][j]`.

## Dữ liệu ra

In ra một số nguyên duy nhất là chi phí nhỏ nhất.

## Ràng buộc

- `1 <= R, C <= 1000`
- `1 <= a[i][j] <= 10^9`
- Trong toàn bộ test, số ô đủ để thuật toán `O(RC log(RC))` chạy được.

## Subtask

- Subtask 1: `R, C <= 5`.
- Subtask 2: `R, C <= 100`.
- Subtask 3: Không có ràng buộc bổ sung.

## Ví dụ

```text
3 3
1 5 1
1 1 1
9 9 1
```

```text
5
```

## Giải thích ví dụ

Một đường đi tối ưu là:

`(1,1) -> (2,1) -> (2,2) -> (2,3) -> (3,3)`

Tổng chi phí là `1 + 1 + 1 + 1 + 1 = 5`.

✅ Đã AC: 1 / 1 submissions