NK05DSRT - Sa mạc

Bài toán

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 <= 200
• 1 <= L <= 30,000 
• Thời gian chạy: 1 giây
• Giới hạn mã nguồn: 5000B
• Bộ nhớ:  1536MB
• Kết quả không quá giới hạn của longint trong pascal và int trong C++

Ví dụ

Input
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 

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

Giải thuật

- Sử dụng thuật toán tìm đường đi có trọng số nhỏ nhất - thuật toán Dijkstra
- Ta sẽ tìm đường đi từ đỉnh N về đỉnh 1
- Khi đang xét đỉnh u, ta tìm các đỉnh kề với u (gọi là v) và tìm lượng nước nhỏ nhất cần có ở v để có thể mang được tới u. Nếu sức mang của Bờm không đủ (C<L+lượng nước cần ở đỉnh u) thì Bờm phải đi về lấy thêm cho đến khi nào đủ. Nếu C<=2*L thì Bờm không thể có nước để tích trữ, coi như không có cạnh nối hai điểm này.

Mã nguồn

- ideone.com
- github.com