Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [C] Đường đi chi phí nhỏ nhất qua lưới chi phí vận chuyển

    Bản đồ vận chuyển là lưới m×nm \times nm×n, mỗi ô gijg_{ij}gij​ là chi phí khi đi qua. Tài xế xuất phát ở (0,0)(0, 0)(0,0), đến đích (m−1,n−1)(m-1, n-1)(m−1,n−1), mỗi bước xuống hoặc sang phải.

    Hãy tính tổng chi phí nhỏ nhất (gồm cả ô đầu và ô cuối).

    Ví dụ lưới [131151421]\begin{bmatrix} 1 & 3 & 1 \\ 1 & 5 & 1 \\ 4 & 2 & 1 \end{bmatrix}​114​352​111​​ có tổng nhỏ nhất là 777 (đi 1→3→1→1→11 \to 3 \to 1 \to 1 \to 11→3→1→1→1).

    • Định dạng đầu vào:

      Dòng 1: mmm, nnn. mmm dòng tiếp, mỗi dòng nnn số nguyên.

    • Ràng buộc đầu vào:

      1≤m,n≤5001 \le m, n \le 5001≤m,n≤500, 0≤gij≤1040 \le g_{ij} \le 10^40≤gij​≤104.

    • Định dạng đầu ra:

      Một số nguyên — tổng chi phí nhỏ nhất.

    Ví dụ:

    Đầu vào:

    3 3
1 3 1
1 5 1
4 2 1

    Đầu ra:

    7

    Giải thích:

    Đường 1→3→1→1→1 cho tổng 7.

    Đang tải editor...