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ò

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/cheer


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
2015-10-04 16:12:08 [Nghien] Le Long
nhớ để kết quả là int64 nhé
2015-07-29 11:25:24 N�ng D�n John
Kruskal vẫn AC nhé :))) [nongdanjohn]
2015-06-24 16:51:59 Do Hong Huan
Bài hay
2015-06-15 12:10:45 there's no salvation for me...
bài này phải dùng prim ms AC
2014-08-24 02:51:18 Nguyễn Ðức Linh
dự là có vụ thông bò
2014-07-24 13:45:51 Thcs Ðặng Chánh Kỷ
fillchar mảng cha=0 thì đc 70 , fillchar mảng cha =-1 thì ac, sao lại vậy chứ
2014-07-04 10:38:52 Xiao Lang
Only Kruskal đấm phát chết luôn
2014-05-22 07:14:58 Nắng
1 đấm AC :v
2013-08-19 04:01:46 Nhung anh sao dem
P là số cạnh của đồ thị ban đầu hay là số cạnh tối đa được loại bỏ khỏi đồ thị?
2012-12-18 15:53:53 sharing
kruskal bình thường chỉ gán lại trọng số thôi. tinh tế là ở chỗ ấy :))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.