REVAMP - Revamping Trails
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Farmer John sẵn lòng kiểm tra những chú bò mỗi ngay. Anh ta đi ngang một số trong M (1 <= M <= 50,000) đường mòn được đánh số từ 1 đến M từ bãi cỏ 1, tất cả đường đi đến bãi cỏ N (một hành trình sẽ tồn trại trong bản đồ trong dữ liệu kiểm tra). N bãi cỏ (1 <= N <= 10,000) được đánh số liên tiếp 1..N, trong trang trại của Farmer John, được nối bằng những đường mòn hai chiều. Mỗi đường mòn i nối bãi cỏ P1_i và P2_i (1 <= P1_i <= N; 1 <= P2_i <= N) và yêu cầu T_i (1 <= T_i <= 1,000,000) đơn vị thời gian để đi qua.
Anh ta muốn sử lại một số đường mòn trong trang trại để tiết kiệm thời gian trong hành trình của anh ta. Đặc biệt, anh ta sẽ chọn K (1 <= K <= 20) đường mòn thành đường cao tốc, mà thời gian sẽ giảm xuống 0. Hãy giúp FJ chọn những đường mòn để tối thiểu thời gian từ bãi cỏ 1 đến N.
Dữ liệu
* Dòng 1: Ba số nguyên cách nhau: N, M, and K
* Dòng 2..M+1: Dòng i+1 miêu tả đường mòn i với ba dấu cách nhau: P1_i, P2_i, and T_i
Kết quả
* Dòng 1: Chiều dài ngắn nhất sẽ khi sửa không nhiều hơn K đường mòn
Ví dụ
Dữ liệu:
4 4 1
1 2 10
2 4 10
1 3 1
3 4 100
Kết quả
1
- Người up: hphong
- Nguồn bài: USACO Feb,2009