Duyên Hải 2020 - Lớp 10 - Bài 3 - Phục vụ

Xem dạng PDF

Gửi bài giải


Điểm: 0,60 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một công ty cung cấp dịch vụ cho các đối tác của mình đặt tại ~n~ vùng khác nhau được đánh số ~1~, ~2~, ~3~, ..., ~n~. Công ty có ~3~ nhân viên phục vụ lưu động. Nếu xuất hiện một yêu cầu tại một địa điểm mà hiện đang không có nhân viên đang ở đó, một trong ba nhân viên di chuyển từ vị trí hiện tại của anh ta đến trực tiếp địa điểm xuất hiện yêu cầu mà không qua bất kỳ một địa điểm trung gian nào khác. Tại mọi thời điểm, chỉ có một nhân viên di chuyển. Các nhân viên chỉ di chuyển khi có yêu cầu phục vụ và không có hai nhân viên nào ở cùng một vị trí tại bất kỳ thời điểm. Chi phí để di chuyển từ vị trí ~i~ đến vị trí ~j~ là ~C_{ij}~. Chú ý rằng hàm chi phí không nhất thiết phải là đối xứng, tuy nhiên chi phí khi không di chuyển luôn bằng ~0~ ~(C_{ii} = 0)~. Các yêu cầu phải được thực hiện theo thứ tự xuất hiện (yêu cầu xuất hiện trước phải được phục vụ trước, phục vụ xong một yêu cầu mới phục vụ yêu cầu tiếp theo).

Yêu cầu: Hãy tìm lịch di chuyển các nhân viên phục vụ yêu cầu sao cho tổng chi phí là nhỏ nhất.

Input

Dữ liệu vào từ file SERV.INP

  • Dòng đầu tiên chứa hai số nguyên dương ~n~, ~m~, lần lượt là số vùng khác nhau và số yêu cầu cần phục vụ ~(3 \leq n \leq 200~, ~1 \leq m \leq 1000)~.
  • ~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên không âm có giá trị không vượt quá ~2000~. Số thứ ~j~ của dòng thứ ~i~ là giá trị của Cij - chi phí để đi từ ~i~ đến ~j~.
  • Dòng cuối cùng chứa ~m~ số nguyên là danh sách các yêu cầu phục vụ theo thứ tự đăng ký. Mỗi yêu cầu được mô tả bằng một số nguyên - số hiệu địa điểm, nơi yêu cầu xảy ra. Ban đầu ba nhân viên phục vụ đang ở các địa điểm ~1~, ~2~ và ~3~.

Output

Ghi ra file SERV.OUT một số nguyên ~S~ là tổng chi phí nhỏ nhất tìm được.

Giới hạn

  1. ~(35~ điểm~)~ ~3 \leq n~, ~m \leq 8~
  2. ~(30~ điểm~)~ ~8 < n~, ~m \leq 50~
  3. ~(35~ điểm~)~ ~50 < n \leq 200~, ~50 < m \leq 1000~

Sample Input

5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1

Sample Output

5

Note

Một phương án tối ưu là ~(1~, ~2~, ~1~, ~2~, ~2~, ~1~, ~3~, ~1~, ~3)~. Ở đây số thứ ~i~ là số hiệu của nhân viên phục vụ yêu cầu thứ ~i~


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.