KPATH - Đồng Eris nhiều nhất
View as PDFVương quốc Belzerg là một vương quốc vô cùng rộng lớn với N thị trấn và M con đường 1 chiều nối giữa các thị trấn. Con đường thứ i (1 ≤ i ≤ M) nối thị trấn ~u_i~ đến thị trấn ~v_i~ . Kazuma là một anh hùng nổi tiếng của thị trấn Axel với biết bao chiến công lẫy lừng. Một ngày nọ anh vào cửa hàng để mua một thanh kiếm mới và đặt tên nó sao thật ngầu, nhưng chưa kịp đặt tên thì một đồng bọn của anh là Megumin đã lấy thanh kiếm và đặt ngay cái tên Chunchunmaru cho nó. Megumin ra điều kiện cho anh nếu muốn lấy lại và đổi tên thanh kiếm: cho anh K ngày, mỗi ngày anh phải đi từ một thị trấn đến thị trấn khác bằng những con đường đã cho và kiếm được nhiều đồng Eris nhất có thể bằng cách chiến đấu với quái vật trên các con đường (chiến đấu với quái vật trên con đường thứ i sẽ được wi đồng Eris, quái vật sẽ hồi sinh sau mỗi ngày). Megumin cũng ra điều kiện rằng Kazuma phải đi chính xác K con đường không thì cô ấy sẽ dùng phép “EXPLOSION!!!” lên thanh kiếm mới của anh, cô ấy cũng thấy rất tội lỗi nên cho phép Kazuma xuất phát từ thị trấn bất kì và được đi lại các thị trấn cũng như các đường mà anh đã đi qua. Kazuma rất muốn lấy lại và đổi tên thanh kiếm mới này vì anh đã để dành biết bao nhiêu tiền từ các nhiệm vụ để mua được nó. Kazuma muốn nhờ các bạn tìm một lộ trình đi qua chính xác K con đường trong K ngày ấy sao cho tổng số đồng Eris kiếm được là nhiều nhất có thể nhé! Dữ liệu:
- Dòng đầu gồm 3 số N, M, K (1 ≤ N ≤ 100, 1 ≤ M ≤ 10000, 1 ≤ K ≤ ~10^9~).
- M dòng tiếp theo, dòng thứ i gồm bộ ba số ~u_i~, ~v_i~, ~w_i~ trong đó (1 ≤ ~u_i~, ~v_i~ ≤ N) và 1 ≤ ~w_i~ ≤ ~10^9~. Kết quả: 1 dòng duy nhất là tổng số đồng Eris kiếm được nhiều nhất trên lộ trình ấy, nếu không có lộ trình nào thỏa mãn thì in ra -1.
Ví dụ:
INPUT 1
4 4 6
1 2 10
2 3 3
3 4 3
4 2 3
OUTPUT 1
25
INPUT 2
4 5 4
1 2 10
2 3 3
3 4 3
1 4 5
2 4 7
OUTPUT 2
-1
Ràng buộc:
- 40% số test có K ≤ 100.
- 60% còn lại không có ràng buộc gì thêm.
Comments
ae dam matrix multiplication nhung toi dam sparse table xong 49/50 cay no dai bum bum