Nhà khảo cổ Benjamas đang chạy thoát thân sau khi khám phá thành phố ngầm bí ẩn của Cá Sấu. Thành phố có \(N\) căn phòng và \(M\) hành lang hai chiều, mỗi hành lang nối một cặp phòng khác nhau gồm hai phòng phân biệt. Thời gian chạy qua các hành lang có thể khác nhau. Trong số \(N\) căn phòng, chỉ có \(K\) phòng là lối ra cho phép cô thoát khỏi thành phố. Benjamas bắt đầu ở phòng \(0\) và muốn đến một phòng có lối ra nhanh nhất có thể.

Tên gác cổng Cá Sấu muốn ngăn Benjamas trốn thoát. Từ hang của mình, hắn điều khiển các cánh cửa bí mật để chặn một hành lang bất kỳ. Tại mỗi thời điểm chỉ một hành lang có thể bị chặn: mỗi khi chặn một hành lang mới, hắn phải mở lại hành lang đã chặn trước đó.

Mỗi lần Benjamas định rời một căn phòng, Cá Sấu có thể chọn chặn một hành lang kề với phòng đó. Sau đó, Benjamas chọn một hành lang không bị chặn và đi theo nó đến phòng tiếp theo. Khi cô đã đi vào một hành lang, Cá Sấu không được chặn hành lang ấy cho đến khi cô đến đầu bên kia. Khi cô vào phòng tiếp theo, hắn lại có thể chọn chặn một hành lang đi ra khỏi phòng đó, kể cả hành lang cô vừa đi qua. Quá trình cứ tiếp tục như vậy.

Benjamas muốn chuẩn bị trước một kế hoạch thoát hiểm đơn giản: một tập hợp chỉ dẫn cho biết phải làm gì khi đến từng căn phòng. Xét phòng \(A\). Nếu đó là phòng có lối ra thì không cần chỉ dẫn, vì cô có thể thoát khỏi thành phố ngay. Nếu không, chỉ dẫn cho phòng \(A\) phải có một trong hai dạng sau:

• “Nếu đến phòng \(A\), hãy đi theo hành lang dẫn đến phòng \(B\). Tuy nhiên, nếu hành lang đó bị chặn thì hãy đi theo hành lang dẫn đến phòng \(C\).”
• “Không cần quan tâm đến phòng \(A\); nếu làm theo kế hoạch này thì không thể đến phòng đó.”

Trong một số trường hợp, chẳng hạn khi kế hoạch khiến Benjamas chạy theo một chu trình, Cá Sấu có thể ngăn cô đến lối ra. Một kế hoạch thoát hiểm được gọi là tốt nếu nó bảo đảm Benjamas đến một phòng có lối ra sau một khoảng thời gian hữu hạn, bất kể Cá Sấu hành động như thế nào. Với một kế hoạch tốt, gọi \(T\) là thời gian nhỏ nhất sao cho chắc chắn Benjamas đã đến một lối ra sau thời gian \(T\). Khi đó, ta nói kế hoạch ấy cần thời gian \(T\).

Yêu cầu

Hãy cài đặt hàm có khai báo chính xác trong crocodile.h:

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]);

Các tham số có ý nghĩa như sau:

• N: số phòng, được đánh số từ \(0\) đến \(N-1\).
• M: số hành lang, được đánh số từ \(0\) đến \(M-1\).
• R: mảng số nguyên hai chiều mô tả các hành lang. Với \(0 \le i < M\), hành lang \(i\) nối hai phòng phân biệt R[i][0] và R[i][1]. Không có hai hành lang cùng nối một cặp phòng.
• L: mảng số nguyên một chiều chứa thời gian đi qua các hành lang. Với \(0 \le i < M\), L[i] là thời gian Benjamas cần để chạy qua hành lang \(i\) và \(1 \le L[i] \le 1\,000\,000\,000\).
• K: số phòng có lối ra, với \(1 \le K < N\).
• P: mảng một chiều gồm \(K\) số nguyên phân biệt mô tả các phòng có lối ra. Với \(0 \le i < K\), P[i] là số hiệu phòng có lối ra thứ \(i\). Phòng \(0\) không bao giờ là phòng có lối ra.

Hàm phải trả về thời gian \(T\) nhỏ nhất mà một kế hoạch thoát hiểm tốt có thể đạt được.

Ràng buộc

Mỗi phòng không có lối ra có ít nhất hai hành lang đi ra. Mỗi bộ dữ liệu đều có một kế hoạch thoát hiểm tốt với \(T \le 1\,000\,000\,000\).

Phân nhóm

Giới hạn và giao diện

Giới hạn thời gian CPU là 2 giây; giới hạn bộ nhớ là 256 MB. Không có giới hạn riêng cho ngăn xếp; bộ nhớ ngăn xếp được tính vào tổng bộ nhớ sử dụng.

Thư mục cài đặt là crocodile/. Thí sinh cài đặt crocodile.c, crocodile.cpp hoặc crocodile.pas. Giao diện phía thí sinh là crocodile.h hoặc crocodile.pas; giao diện phía trình chấm là crocodile.h hoặc crocodilelib.pas. Trình chấm mẫu gồm grader.c, grader.cpp, hoặc grader.pas cùng với crocodilelib.pas.

Dữ liệu vào

Trình chấm mẫu đọc các tệp grader.in.1, grader.in.2, ... theo định dạng:

• Dòng \(1\): ba số nguyên \(N\), \(M\), \(K\).
• Các dòng \(2\) đến \(M+1\): với \(0 \le i < M\), dòng \(i+2\) chứa R[i][0], R[i][1], L[i], cách nhau bởi dấu cách.
• Dòng \(M+2\): \(K\) số nguyên P[0], P[1], ..., P[K-1], cách nhau bởi dấu cách.
• Dòng \(M+3\): đáp án mong đợi.

Dữ liệu ra

Các tệp kết quả mẫu grader.expect.1, grader.expect.2, ... đều chứa đúng dòng Correct. khi hàm trả về đáp án đúng.

Ví dụ

5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
7

Correct.

5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14

Correct.

Nguồn

IOI 2011, ngày thi 2, Pattaya, Thái Lan. Đề Crocodile’s Underground City, bản tiếng Anh 1.3: PDF chính thức. Nội dung được dịch từ đề chính thức; tất cả các hình minh họa đều lấy từ đề chính thức. Giao diện C/C++ và dữ liệu của trình chấm mẫu được đối chiếu với bộ API gốc.