Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CHEER - Động viên đàn bò

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274809/problem/M

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 Sj và Ej (1 <= Sj <= N; 1 <= Ej <= N; Sj # Ej) và cần Lj (0 <= Lj <= 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 Ci (1 <= Ci <= 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 Ci

* Dòng N+2..N+P+1: Dòng N+j+1 chứa ba số nguyên phân biệt: Sj, Ej và Lj

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

Được gửi lên bởi:Phong
Ngày:2008-11-11
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:USACO November 2008

hide comments
2010-02-12 00:16:37 dhkhtn
Wake up in pasture 4 and visit pastures in the order 4, 5, 4, 2, 3, 2, 1, 2, 4 yielding a total time of 176 before going back to sleep.

**********************************************************************


Last edit: 2010-02-12 00:19:06
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.