H
hai6f2009
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Ở 1 thành phố beta đang tổ chứ một cuộc đua xe công thức 1. Trước khi cuộc đua diễn ra, người ta muốn thiết kế 1 hệ thống gồm một số camera dọc theo mỗi vòng đua.
Hệ thống đường đua có thể được mô tả bởi các nút giao thông và các đường nối các nút giao thông là đường 2 chiều. Một vòng đua bao gồm 1 nút giao thông xuất phát, tiếp theo là đường di chuyển gồm ít nhất 3 tuyến đường và cuối cùng quay trở lại điểm xphát. Trong 1vòng đua, môtx tuyến đường chỉ được đi qua đúng 1 lần.
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 ko phải nút giao thông.
Yêu cầu: Cho n nút gthông, m tuyến đường nối các nút giao thông và chi phí đặt camera trên mỗi tuyến đường. Hãy chọn một số tuyến đường lắp đặt camera sao cho tổng chi phí lắp đặt là thấp nhất.
Dữ liệu: cho vào file 'RACING.INP' có nội dung như sau:
- dòng 1: ghi 2 số n, m (1<= n<=1000;1<=m<=10000) là số nút giao thông và số tuyến đường. Các nút giao thông được đánh số từ 1 đến n.
-m dòng tiếp theo gồm 2 số u,v là tuyến đường nối 2 nút giao thông u và v và chi phí lắp đặt camera tại tuyến đường đó là c(1<=c<=1000).
- Dữ liệu luôn đảm bảo 2 nút giao thông bất kì đều có thể đi đến được với nhau bằng tuyến đường tiếp hoặc qua các tuyến đường trung gian. Các số cách nhau bới dấu cách
Kết quả ghi vào file 'RACING.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ụ:
RACING.INP
6 7
1 2 5
2 3 3
1 4 5
4 5 4
5 6 4
6 3 3
5 2 3
RACING.OUT
6
Hệ thống đường đua có thể được mô tả bởi các nút giao thông và các đường nối các nút giao thông là đường 2 chiều. Một vòng đua bao gồm 1 nút giao thông xuất phát, tiếp theo là đường di chuyển gồm ít nhất 3 tuyến đường và cuối cùng quay trở lại điểm xphát. Trong 1vòng đua, môtx tuyến đường chỉ được đi qua đúng 1 lần.
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 ko phải nút giao thông.
Yêu cầu: Cho n nút gthông, m tuyến đường nối các nút giao thông và chi phí đặt camera trên mỗi tuyến đường. Hãy chọn một số tuyến đường lắp đặt camera sao cho tổng chi phí lắp đặt là thấp nhất.
Dữ liệu: cho vào file 'RACING.INP' có nội dung như sau:
- dòng 1: ghi 2 số n, m (1<= n<=1000;1<=m<=10000) là số nút giao thông và số tuyến đường. Các nút giao thông được đánh số từ 1 đến n.
-m dòng tiếp theo gồm 2 số u,v là tuyến đường nối 2 nút giao thông u và v và chi phí lắp đặt camera tại tuyến đường đó là c(1<=c<=1000).
- Dữ liệu luôn đảm bảo 2 nút giao thông bất kì đều có thể đi đến được với nhau bằng tuyến đường tiếp hoặc qua các tuyến đường trung gian. Các số cách nhau bới dấu cách
Kết quả ghi vào file 'RACING.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ụ:
RACING.INP
6 7
1 2 5
2 3 3
1 4 5
4 5 4
5 6 4
6 3 3
5 2 3
RACING.OUT
6