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.|

NKRACING - Vòng đua F1

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/nkracing


Singapore sẽ tổ chức một cuộc đua xe Công Thức 1 vào năm 2008. Trước khi cuộc đua diễn ra, đã xuất hiện một số cuộc đua về đêm trái luật. Chính quyền muốn thiết kế một hệ thống kiểm soát giao thông để bắt giữ các tay đua phạm luật. Hệ thống bao gồm một số camera đặt trên các tuyến đường khác nhau. Để đảm bảo tính hiệu quả cho hệ thống, cần có ít nhất một camera dọc theo mỗi vòng đua.

Hình minh họa

Hệ thống đường ở Singapore có thể được mô tả bởi một dãy các nút giao thông và các đường nối hai chiều (xem hình vẽ). Một vòng đua bao gồm một nút giao thông xuất phát, tiếp theo là đường đi bao gồm ít nhất 3 tuyến đường và cuối cùng quay trở lại điểm xuất phát. Trong một vòng đua, mỗi tuyến đường chỉ được đi qua đúng một lần, theo đúng một hướng.

Chi phí để đặt camera phụ thuộc vào tuyến đường được chọn. Các số nhỏ trong hình vẽ cho biết chi phí để đặt camera lên các tuyến đường. Các số lớn xác định các nút giao thông. Camera được đặt trên các tuyến đường chứ không phải tại các nút giao thông. Bạn cần chọn một số tuyến đường sao cho chi phí lắp đặt là thấp nhất đồng thời vẫn đảm bảo có ít nhất một camera dọc theo mỗi vòng đua.

Viết chương trính tìm cách đặt các camera theo dõi giao thông sao cho tổng chi phí lắp đặt là thấp nhất.

Hình minh họa

Dữ liệu

  • Dòng đầu tiên chứa 2 số nguyên n, m ( 1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000) là số nút giao thông và số đường nối. Các nút giao thông được đánh số từ 1 đến n.
  • m dòng tiếp theo mô tả các đường nối, mỗi dòng bao gồm 3 số nguyên dương cho biết hai đầu mút của tuyến đường và chi phí lắp đặt camera. Chi phí lắp đặt thuộc phạm vi [1, 1000].

Kết qủa

In ra 1 số nguyên duy nhất là tổng chi phí lắp đặt thất nhất tìm được.

Ví dụ

Dữ liệu:
6 7
1 2 5
2 3 3
1 4 5
4 5 4
5 6 4
6 3 3
5 2 3

Kết qủa
6

Được gửi lên bởi:Jimmy
Ngày:2007-12-23
Thời gian chạy:1s
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 PERL6 PYPY RUST SED
Nguồn bài:ACM Singapore Regional 2007

hide comments
2014-12-28 03:21:32 Prismatic
=)))
2014-12-09 17:34:58 Huỳnh Ngọc Ðỉnh
quá buồn @@
không nên màu mè @@

Last edit: 2014-12-09 18:36:36
2014-08-27 18:38:03 Thcs Ðặng Chánh Kỷ
bài siêu dễ, hồi đó ngất ngất để mảng cha=0, thay bằng -1 phát ac luôn , dại dột 1 thời trẻ trâu
2014-08-07 12:50:18 ■■‡[ND] Bee Sociu■■‡
Please be careful, leave short comments only. Don't spam here.
2014-07-22 11:01:07 nguyễn vãn lâm
Dieu minh ko hieu la, tai sao ko lap 1 camera thui. Ma lai lap 2? B nao giai thich gium minh voi.thank
2014-07-20 05:09:54 nguyên hữu ðạt
lam kiểu gì thế mấy bạn
2014-07-03 09:05:52 _sanghk11_
dữ liệu càng lớn điểm càng thấp.........

Last edit: 2014-07-03 10:58:41
2014-03-27 15:31:37 Thcs Ðặng Chánh Kỷ
bài này phải dùng bản ghi mới ac được định mệnh dùng 3 mảng được có 80
2013-11-27 17:31:08 Xiao Lang
Tổng trọng số -Cây khung lớn nhất có N-1 cạnh => AC
2013-11-04 14:39:32 Le Khac Nam
cai nay co lien thong ko nhi
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.