VI KHUẨN VIKHUAN (7 ĐIỂM) MỘT CÂY RONG TẢO KHỔNG LỒ CÓ CẤU TẠO...

Bài 3. Vi khuẩn VIKHUAN (7 điểm)

Một cây rong tảo khổng lồ có cấu tạo như một đồ thị và là một cây với N nút (các nút được đánh số từ

1 đến N) . Tại một số nút của cây, mỗi nút trong số này có một cá thể vi khuẩn đang trú ngụ và không

di chuyển. Vào thời điểm 0, tại một nút P có một lượng độc tố đủ để lan tỏa liên tục không ngừng với

tốc độ 1 đơn vị chiều dài trên một đơn vị thời gian và có thể giết chết mọi vi khuẩn tiếp xúc với nó.

Yêu cầu: cho biết thông tin đầy đủ về cây rong tảo, số lượng vi khuẩn và nơi trú ngụ, vị trí xuất phát

của lượng độc tố (nút P), hãy cho biết thời điểm sớm nhất T mà số lượng vi

khuẩn bị giết vượt quá nửa tổng số vi khuẩn có vào trước thời điểm 0.

Input Output

Input

10

2

 Dòng đầu tiên ghi số N (1 ≤ N ≤ 1000)

7

 Dòng thứ hai ghi số P (1 ≤ P ≤ N)

1 2 3 5 9 10

 Dòng thứ ba ghi danh sách các nút có vi khuẩn đang trú ngụ (danh

4 10 35

sách này có ít nhất 1 nút)

10 5 68

 N – 1 dòng cuối cùng ghi độ dài của một đoạn cây rong tảo nối hai

6 4 111

nút kề nhau, mỗi dòng có dạng một bộ ba số nguyên I, J, L cho biết

10 7 31

đoạn nối nút I với nút J có độ dài L ( 1 ≤ L ≤ 30000)

3 2 74

Output:số nguyên T, là thời điểm sớm nhất tìm được.

9 3 67

Ràng buộc: 50% số test ứng với 50% số điểm của bài có N ≤ 200. Thời

3 8 92

gian giới hạn với mỗi test: 01 giây.

4 2 88

1 6 42