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

    solution

    Đề bài: [Giải thuật] Đường đi nhỏ nhất trên lưới có chướng ngại

    Cho lưới r×cr \times cr×c gồm các ô. Ô có giá trị −1-1−1 là chướng ngại không đi qua được, ngược lại là chi phí dương khi bước vào ô. Bắt đầu ở ô (1,1)(1,1)(1,1), đích ở ô (r,c)(r,c)(r,c), mỗi bước chỉ đi sang phải hoặc xuống dưới. Tìm tổng chi phí nhỏ nhất (tính cả ô đầu và ô cuối). Nếu không có đường đi, in −1-1−1.

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

      Dòng đầu rrr và ccc. rrr dòng sau, mỗi dòng ccc số nguyên.

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

      1≤r,c≤10001 \le r, c \le 10001≤r,c≤1000. Ô không chướng ngại có giá trị 1≤aij≤1061 \le a_{ij} \le 10^61≤aij​≤106.

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

      In chi phí nhỏ nhất, hoặc −1-1−1 nếu không tới được.

    Ví dụ:

    Đầu vào:

    2 2
1 2
3 4

    Đầu ra:

    7

    Giải thích:

    Đường 1->2->4 = 7, đường 1->3->4 = 8; nhỏ nhất là 7.

    Đang tải editor...