Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
Diễn đàn arrow Thư viện arrow Đề thi arrow IOI (thi quốc tế) arrow 2003 arrow Duy trì đường mòn (Trail Maintenance)
Duy trì đường mòn (Trail Maintenance) In E-mail
(3 votes)
Người viết: Ngô Minh Đức   
21/04/2008
Bài toán: Duy trì đường mòn (Trail Maintenance)
Những con bò của bác nông dân Jonh muốn được tự do đi lại giữa N (1≤N≤200) cánh đồng (đánh số 1..N) của trang trại, mặc dù giữa các cánh đồng bị ngăn cách bởi những rừng cây. Các con bò muốn sử dụng những tuyến đường mòn nối liền các cặp cánh đồng để đi. Bò có thể di chuyển trên các con đường theo cả hai chiều.
Các con bò không tự làm được đường, thay vào đó, chúng sử dụng đường đi của động vật hoang dã mà chúng phát hiện ra. Hàng tuần, các con bò cần lựa chọn một số hay tất cả các tuyến đường chúng biết để duy trì.
Đầu mỗi tuần, các con bò lại phát hiện thêm một đường đi mới của động vật hoang dã. Chúng phải quyết định tập hợp các con đường mà chúng phải duy trì sao cho trong tuần đó chúng có thể đi lại từ cánh đồng này tới cánh đồng khác một cách bất kỳ. Bò chỉ có thể sử dụng các con đường mà hiện chúng đang duy trì khi di chuyển.
Các con bò luôn mong muốn tổng chiều dài các đường mòn phải duy trì là nhỏ nhất. Bò có thể chọn duy trì bất kỳ con đường nào trong số chúng biết, dù cho đường đi đó có được duy trì ở tuần trước hay không.
Đường đi của động vật hoang dã (kể cả khi được duy trì) không bao giờ thẳng. Hai tuyến đường nối cùng một cặp cánh đồng có thể có chiều dài khác nhau. Các tuyến đường cũng có thể cắt nhau, tuy nhiên, bò không thay đổi đường đi trừ khi chúng ở trên cánh đồng.
Cứ vào đầu tuần, các con bò sẽ cho bạn biết đường đi mới của động vật hoang dã mà chúng vừa phát hiện được. Chương trình của bạn phải chỉ ra tổng ngắn nhất chiều dài các con đường mà bò cần duy trì để trong tuần đó, chúng có thể đi đến mọi cánh đồng, tất nhiên, nếu tồn tại các tuyến đường như vậy.
Input: Standard input
Dòng đầu tiên của tệp input bao gồm hai số nguyên, cách nhau bởi dấu trắng, N và W, trong đó W là số tuần mà chương trình cần tính toán. (1≤W≤6000)
Với mỗi tuần, đọc một dòng chứa thông tin về đường đi của động vật hoang dã được phát hiện. Dòng này chứa 3 số nguyên, cách nhau bởi dấu trắng, bao gồm: số hiệu các cánh đồng hai đầu đường đi và chiều dài con đường (1..10000). Số hiệu cánh đồng hai đầu tuyến đường luôn khác nhau.
Output: Standard output
Ngay sau khi biết thông tin về đường đi của động vật hoang dã mới được phát hiện, chương trình của bạn cần đưa ra một dòng trên đó bao gồm tổng chiều dài ngắn nhất của các con đường mà bò phải duy trì. Nếu không tồn tại các đường đi cho phép bò di chuyển đến mọi cánh đồng, đưa ra số -1.
Chương trình của bạn phải kết thúc ngay sau khi xử lý tuần cuối cùng.
Ví dụ:

Hạn chế:
Thời gian chạy chương trình là 1 giây
Bộ nhớ 64MB
Cho điểm:
Bạn sẽ nhận được điểm tối đa cho mỗi bộ test nếu chương trình của bạn đưa ra kết quả đúng.
 
Tiếp >