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.|

REVAMP - Revamping Trails

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/revamp


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


Được gửi lên bởi:Phong
Ngày:2009-02-13
Thời gian chạy:0.200s
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 NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:USACO Feb,2009

hide comments
2010-12-13 03:52:22 xuanson94
chan
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.