KPATH - Đồng Eris nhiều nhất

View as PDF

Submit solution

Points: 500.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Vươ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

Please read the guidelines before commenting.



  • -1
    HuanHoaHoe  commented on May 15, 2024, 5:09 p.m.

    ae dam matrix multiplication nhung toi dam sparse table xong 49/50 cay no dai bum bum


  • 17
    kieulqd  commented on Oct. 8, 2020, 7:50 a.m.
    • Với K nhỏ: Ta có thể dùng qhđ F[i][j] là đường đi có số tiền nhận được lớn nhất khi đến đỉnh i và đã đi qua j cạnh. Kết quả sẽ là ∑_(i=1)^N▒〖F[i][k]〗
    • K lớn Ta sẽ sử dụng nhân ma trận với ma trận trung gian có dạng f[i][j] = -1 với mọi i, j ≤ N, f[ui][vi] = wi với 1 ≤ i ≤ M. Nhân 2 ma trận a, b thì ta duyệt tất cả các đỉnh u, v cho ma trận kết quả rồi cập nhật f[u][v] = max(a.f[u][t] + b.f[t][v]) với t là đỉnh trung gian để đi u->t->v và f[u][t] với f[t][v] phải khác -1. Từ đó ta được f[u][v] là đường đi nhận được số tiền lớn nhất từ u->v. Ma trận kết quả cuối cùng sẽ là (Ma trận trung gian)k, đặt là res thì kết quả của bài toán là max(res[u][v]) với mọi 1 ≤ u, v ≤ N.