CHEER - Động viên đàn bò
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Bác John dạo này lười đến nỗi không muốn bảo trì các con đường dẫn bác đến thăm N (5 <= N <= 10,000) cánh đồng (đánh số từ 1 đến N) nữa. Mỗi cánh đồng là nơi ở của một cô bò. Bác John có kế hoạch loại bỏ nhiều nhất P (N-1 <= P <= 100,000) con đường sao cho các cánh đồng vẫn liên thông.
Ban phải xác định N-1 con đường cần giữ lại.
Đường nối hai chiều j nối giữa cánh đồng S j và E j (1 <= S j <= N; 1 <= E j <= N; S j # E j ) và cần L j (0 <= L j <= 1000) thời gian để di chuyển. Không có hai cánh đồng nào được nối trực tiếp bởi nhiều hơn một con đường.
Đàn bò buồn vì hệ thống giao thông của chúng sắp bị rút gọn. Bạn phải thăm mỗi cô bò ít nhất một lần trong ngày để động viên. Mỗi lần thăm cánh đồng i (dù chỉ đi ngang qua), bạn phải trò chuyện với cô bò trong thời gian C i (1 <= C i <= 1000).
Bạn sẽ nghỉ lại đêm trên cùng một cánh đồng (bạn sẽ được chọn) cho đến khi đàn bò đều đã hết bị suy sụp. Bạn sẽ trò chuyện với cô bò trong cánh đồng mà bạn nghỉ lại ít nhất 2 lần vào buổi sáng thức dậy và vào buổi tối khi trở về nghỉ.
Giả dụ bác John theo lời khuyên của bạn giữ lại một số con đường và bạn sẽ chọn cánh đồng tối ưu nhất để nghỉ lại, hãy xác định thời gian nhỏ nhất bạn cần để thăm tất cả đàn bò ít nhất một lần trong ngày.
Dữ liệu
* Dòng 1: Hai số nguyên N và P cách nhau bởi khoảng trắng
* Dòng 2..N+1: Dòng i+1 chứa một số nguyên duy nhất C i
* Dòng N+2..N+P+1: Dòng N+j+1 chứa ba số nguyên phân biệt: S j , E j và L j
Kết quả
* Dòng 1: Một số nguyên duy nhất, tổng thời gian cần để thăm tất cả đàn bò (bao gồm hai lần thăm cô bò ở nơi mà bạn nghỉ).
Ví dụ
Dữ liệu: 5 7 10 10 20 6 30 1 2 5 2 3 5 2 4 12 3 4 17 2 5 15 3 5 6 4 5 12 Kết quả: 176
- Người up: hphong
- Nguồn bài: USACO November 2008