Hotline : +84 0988.131.808       endefr
  1. Bac nam
  2. Thảo luận Internet CNTT
  3. Thứ năm, Tháng 3 16 2017, 02:46 PM
  4.  Đăng ký qua email

Nông dân John đang ở trên một con thuyền nhỏ và đang tìm kiếm kho báu ở 1 trong số N (1 <= N <= 100) hòn đảo (đánh số từ 1..N) ở vùng biển Ca-ri-bò.

Bản đồ kho báu cho John biết John cần phải thực hiện 1 hành trình đi qua đảo A_1, A_2, … A_M (2 <= M <= 10,000), bắt đầu từ đảo 1 và kết thúc ở đảo N trước khi kho báu biến mất. Anh ta có thể đến thăm các đảo khác và thăm bao nhiêu lần tùy thích, miễn là hành trình của ông ta phải chứa dãy A_1,..A_M là 1 dãy con (không nhất thiết phải liên tiếp nhau).

John muốn tránh đụng độ cướp biển và biết được mức-độ-bị-cướp (0 <= mức-độ-bị-cướp <= 100,000) khi đi lại giữa 2 hòn đảo với nhau. Độ nguy hiểm của hành trình của John sẽ là tổng các mức-độ-bị-cướp trên các tuyến đường mà John đi qua.

Hãy giúp John tìm được 1 hành trình ít nguy hiểm nhất để có thể lấy được kho báu.

Dữ liệu

  • Dòng 1: 2 số nguyên cách nhau bởi dấu cách: N và M
  • Dòng 2..M+1: Dòng i+1 mô tả chứa 1 số nguyên là đảo thứ i mà John cần phải tới: A_i
  • Dòng M+2..N+M+1: Dòng i+M+1 chứa N số nguyên cách nhau bởi dấu cách tương ứng là mức-độ-bị-cướp trên tuyến đường đi giữa đảo i và đảo 1, 2,…N; đảm bảo số nguyên thứ i luôn là số 0.
Bình luận
Không có ý kiến đóng góp nào.
Thêm bình luận
Facbook Chấp nhận Trả lời
0
Bầu chọn

Kết quả

  • Dòng 1: Độ nguy hiểm nhỏ nhất của hành trình của John.

Ví dụ

Dữ liệu
3 4
1
2
1
3
0 5 1
5 0 2
1 2 0

Giải thích:
Có 3 hòn đảo và bản đồ kho báu yêu cầu John phải thực hiện 1 hành 
trình tới các đảo như sau: từ đảo 1 tới đảo 2, quay lại đảo 1 và cuối 
cùng là tới đảo 3. Mức-độ-bị-cướp trên các tuyến đường đã được 
cho: (1, 2); (2, 3); (3, 1) có độ lớn tương ứng là 5, 2 và 1.

Kết quả
7

Giải thích:
Hành trình có độ nguy hiểm nhỏ nhất là 7. John sẽ đi như sau: 
1, 3, 2, 3, 1, and 3. Yêu cầu của bản đồ là phải chứa dãy
(1, 2, 1, và 3) và hành trình này thỏa mãn yêu cầu. Chúng ta sẽ tránh đi 
trên đường nối giữa 2 đảo 1 và 2 vì nó có mức-độ-bị-cướp lớn.
Bình luận
Không có ý kiến đóng góp nào.
Thêm bình luận
  1. hơn một tháng trước đây
  2. Thảo luận Internet CNTT
  3. Trả lời này
  • Trang :
  • 1


Không có trả lời ở đây.
khách
Gửi phản hồi của bạn
Tải lên tập tin hoặc hình ảnh cho cuộc thảo luận này bằng cách nhấp vào nút tải ở dưới. hỗ trợ gif,jpg,png,zip,rar
• Xóa s (Maximum File Size: 2 MB)
Bạn có thể chèn các thăm dò ý kiến vào bài viết của bạn. Các cuộc thăm dò sau đó sẽ xuất hiện trong bài viết.
Tùy chọn bỏ phiếu
Chia sẻ vị trí

Chia sẻ vị trí hiện tại của bạn trong khi đăng một câu hỏi mới cho phép người xem để xác định vị trí bạn đang nằm.

Vi độ:
Kinh độ:
  • Bùi Văn Lương
    1897.00 Điểm
  • Hoàng Tiến An
    1502.00 Điểm
  • Phạm Minh Anh
    1335.00 Điểm
  • Hoàng Trung Kiên
    1197.00 Điểm
  • Nguyễn Anh Đông
    1165.00 Điểm
  • Nguyễn Văn Cường
    1042.00 Điểm
  • Hoàng Mạnh Thái
    942.00 Điểm
  • Hoàng Anh Thư
    815.00 Điểm
  • Hoàng Thế Anh
    792.00 Điểm
  • Triệu Hùng Cường
    692.00 Điểm
  • Hoàng Thị Mai
    625.00 Điểm
  • Triệu Mai Anh
    237.00 Điểm
  • Lưu Phương Dung
    162.00 Điểm
  • Phạm Thị Hồng
    142.00 Điểm
  • Hoàng Thế Quỳnh
    87.00 Điểm