Hệ
thống đường 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. 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. 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.
Dữ liệu vào: Từ tệp văn bản
CAMERA.INP
+ Dòng đầu tiên gồm 2 số nguyên dương n và 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ỗi dòng gồm 3 số u, v và c cho biết
chi phí lắp đặt camera từ nút v đến nút u là c. Chi phí lắp đặt trong phạm vi
[1,1000]
Dữ liệu ra: ghi vào tệp văn bản
CAMERA.OUT một số nguyên duy nhất là tổng chi phí lắp đặt thấp nhất tìm được.
Ví dụ:
CAMERA.INP
|
CAMERA.OUT
|
6 7
1 2 5
2 3 3
1 4 5
4 5 4
5 6 4
6 3 3
5 2 3
|
6
|
