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

NK05DSRT - Sa mạc

Bờm vô tình bị lạc vào trong 1 ốc đảo có 1 bộ tộc thổ dân sinh sống trong 1 lần đi qua sa mạc. Bờm muốn thoát khỏi sa mạc để về nhà. Người thổ dân đã cho anh một bản đồ vùng sa mạc này.

Sa mạc gồm N ốc đảo, M đường đi an toàn nối với nhau và tại mỗi ốc đảo lại có 1 hồ chứa nước rất lớn và nước chứa trong các hồ này không bao giờ cạn. Tuy nhiên hiện tại, không có nước trong các hồ.

Giả sử: Bờm đang ở ốc đảo 1, về để về đến nhà thì Bờm phải đi đến ốc đảo N. Người thổ dân cho biết rằng tại vùng sa mạc này, nếu Bờm đi đoạn đường có độ dài là L, thì Bờm phải mang uống đủ lượng nước là L, bằng không Bờm sẽ chết. Từ đó, người thổ dân đã chỉ cho Bờm cách có thể về nhà: Bờm phải vận chuyển nước từ ốc đảo 1 đển tích trữ trong các hồ tại những ốc đảo khác bằng các con đường an toàn đã có, từ đó anh có thể về nhà. Tuy nhiên, lại có 1 khó khăn khác là: trong bất cứ thời gian nào, Bờm không thể mang lượng nước quá C (do thể lực có hạn ^_^).

Yêu cầu: Hãy tìm cách giúp Bờm về nhà nhưng đồng thời sử dụng ít nước nhất (do trong sa mạc, nước rất quí !!!!)

Dữ liệu vào

Dòng đầu tiên gồm một số nguyên t cho biết số lượng test, mỗi test có dạng như sau:

  • Dòng đầu tiên là 3 số nguyên N M C ngăn cách nhau bởi khoảng trắng
  • M dòng tiếp theo mỗi dòng gồm 3 số nguyên I J L với y nghĩa có đường đi từ ốc đảo I đến ốc đảo J và ngược lại là an toàn và có độ dài L.

Kết qủa

Với mỗi bộ test xuất ra đúng 1 số nguyên chỉ lượng nước ít nhất cần dùng.

Giới hạn

  • 1 <= N, M, C <= 100
  • 1 <= L <= 30,000

Ví dụ

Dữ liệu mẫu
1
9 10 25 
1 2 3 
2 3 12 
3 4 4 
3 5 9 
4 9 13 
5 9 5 
2 6 10 
6 7 10 
7 8 10 
8 9 10 

Kết qủa
65 

Giải thích

Mang 25 nước từ 1 đến 2 sau đó lại quay về 1. Do đó, tại 2 có 19 nước. (Bờm đã uống hết (3 + 3) nước trong lần đi và về, (19 = 25 – 3 – 3)).

Lặp lại như thế 1 lần nữa, Bờm đã mang đến 2 thêm 19 nước. Sau đó lại từ 1, Bờm mang theo 15 nước đến 2. Vậy khi đến 2, Bờm có tại đây (19+19+12 = 50) nước.

Tiếp theo, Bờm lại mang 25 nước đi từ 2 đến 3, rồi quay về 2, như vậy, tại 3 có (25 – 12 – 12 = 1) nước. Từ 2, Bờm mang 25 nước còn lại đi đến 3. Tại 3, Bờm có được (1+(25-12) = 14) nước.

Cuối cùng, Bờm mang 14 nước đi đến 5 rồi đến 9. Vậy là Bờm đã thoát khỏi sa mạc.


Được gửi lên bởi:Duc
Ngày:2005-05-02
Thời gian chạy:0.469s
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:Lê Thành Trung - 3rd VNOPSC

hide comments
2016-10-05 18:44:46
trong trường hợp tất cả các cạnh đều lớn hơn c(không có cách thoát khỏi sa mạc) thì sao nhỉ?
2012-08-20 09:49:19 123
Mình đọc đề trên VNOI ko có comment nên cứ để n<100 => WA cả buổi chiều nản!
2011-08-06 10:19:41 Ðang tập code
Đề bài cho bẫy quá!
2011-06-22 12:24:11 T-7
Kết quả thuộc kiểu Int64 trong pascal hoặc long long trong C
2011-06-22 07:07:26 Ðỗ Việt Anh
trong các test kết quả đều thuộc kiểu 32 bit:).
Lưu ý N<=200 thì phải chứ không phải <= 100 như đề bài :d.

Last edit: 2011-06-22 07:07:51
2011-06-20 10:43:50 Ðỗ Việt Anh
vd test này
N=4; M=3; C=100;
1 2 49
2 3 49
3 4 49
các thử thì thấy lượng nước tăng theo cấp số nhân rất kinh khủng. nếu là 100 thì ????
2011-06-20 10:38:39 Ðỗ Việt Anh
trời mình không tính được lượng nước
trong trường hợp xấu nhất, Nhưng sơ sơ
thì nó cũng là rất rất.. rất lớn.
2010-05-31 15:59:22 Siêu Nhân Trong Suốt
sao Time limit giống của Turbo Pascal :| ,

Last edit: 2010-05-31 17:10:18
2009-04-06 05:04:57 Nguyễn Vãn Phúc
bai nay hay day ban
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.