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

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:Duc
Ngày:2007-12-23
Thời gian chạy:0.25s
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
2017-09-04 16:24:27
kham khảo cách giải ở
https://vietcodes.github.io/code/65/
2017-08-16 21:34:45 Con Bò Huyền Thoại
https://kienthuc24h.com/bai-giai-nkracing-spoj-2245-vong-dua-f1/
2017-08-11 11:09:56
Kruskal 100d, Prim 90d -_-
2017-08-04 11:05:27
Code C++ AC =))
https://ideone.com/URXRIm
2017-05-14 02:02:57
trường hợp đa đồ thị thì sao ?
2017-02-27 14:07:33
Cây khung lớn nhất =))
2016-10-02 06:44:18
Sao mà 90đ hoài v nè @@
2016-04-17 16:20:54
lại Quicksort lộn m với n @@@
2016-04-10 04:54:23 Nguyễn Nam
heap 100 nhé :v
2016-01-15 11:45:55 Lê Thanh Phú
Dung Kuruskal AC 100
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.