Nhân dịp IOI, thành phố Pattaya sẽ tổ chức cuộc đua International Olympiad in Racing (IOR) 2011. Với vai trò chủ nhà, chúng ta phải tìm một đường đua tốt nhất có thể.

Trong vùng đô thị Pattaya–Chonburi có \(N\) thành phố được nối bởi mạng lưới gồm \(N-1\) đường cao tốc. Mỗi đường cao tốc đi được theo cả hai chiều, nối hai thành phố khác nhau và có độ dài nguyên tính bằng kilômét. Giữa mỗi cặp thành phố có đúng một đường đi: chỉ có một cách đi từ thành phố này đến thành phố kia qua một dãy đường cao tốc mà không ghé thành phố nào hai lần.

Quy định của IOR yêu cầu đường đua có tổng độ dài đúng \(K\) kilômét, bắt đầu và kết thúc ở hai thành phố khác nhau. Để tránh va chạm, không đường cao tốc nào, và do đó cũng không thành phố nào, được sử dụng hai lần trong đường đua. Để giảm thiểu ảnh hưởng đến giao thông, đường đua phải sử dụng ít đường cao tốc nhất có thể.

Yêu cầu

Cài đặt hàm sau, được khai báo trong race.h:

int best_path(int N, int K, int H[][2], int L[]);

• N: số thành phố, được đánh số từ \(0\) đến \(N-1\).
• K: độ dài cần có của đường đua.
• H: mảng hai chiều mô tả các đường cao tốc. Với \(0 \le i < N-1\), đường cao tốc \(i\) nối thành phố H[i][0] và thành phố H[i][1].
• L: mảng một chiều chứa độ dài các đường cao tốc. Với \(0 \le i < N-1\), đường cao tốc \(i\) có độ dài L[i].

Mọi phần tử của H nằm trong đoạn từ \(0\) đến \(N-1\), và các đường cao tốc nối tất cả thành phố đúng như mô tả ở trên. Mọi phần tử của L là số nguyên trong đoạn từ \(0\) đến \(1\,000\,000\), kể cả hai đầu; đường cao tốc có thể có độ dài bằng \(0\).

Hàm phải trả về số đường cao tốc ít nhất trong một đường đua hợp lệ có tổng độ dài đúng \(K\). Nếu không tồn tại đường đua như vậy, trả về -1. Không có thủ tục gọi lại để báo đáp án; trình chấm sử dụng giá trị trả về của best_path.

Ví dụ

4 3
0 1 1
1 2 2
1 3 4
2

Correct.

3 3
0 1 1
1 2 1
-1

Correct.

11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2

Correct.

Ràng buộc

Trong mọi nhóm, \(0 \le L[i] \le 1\,000\,000\) với \(0 \le i < N-1\); các đường cao tốc tạo thành mạng lưới như mô tả ở trên.

Phân nhóm

Chi tiết cài đặt

Giới hạn thời gian CPU: 3 giây. Giới hạn bộ nhớ: 256 MB. Không có giới hạn riêng cho bộ nhớ 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à race/. Thí sinh cài đặt race.c, race.cpp hoặc race.pas. Giao diện của thí sinh là race.h hoặc race.pas; giao diện của trình chấm là race.h hoặc racelib.pas. Trình chấm mẫu được cung cấp trong grader.c, grader.cpp hoặc grader.pas.

Dữ liệu vào

Các tệp đầu vào mẫu là grader.in.1, grader.in.2, … Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng \(1\): hai số nguyên \(N\) và \(K\).
• Các dòng \(2\) đến \(N\): thông tin về các đường cao tốc. Dòng \(i+2\) chứa H[i][0], H[i][1] và L[i], cách nhau bởi dấu cách, với \(0 \le i < N-1\).
• Dòng \(N+1\): đáp án mong đợi.

Dữ liệu ra

Kết quả mong đợi tương ứng nằm trong grader.expect.1, grader.expect.2, … Mỗi tệp này chứa đúng văn bản Correct..

Nguồn

IOI 2011, ngày thi 1, Pattaya, Thái Lan. Đề Race, 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.