Matrix Exponentiation - Min Path

View as PDF

Submit solution


Points: 0.80
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
Matrix Exponentiation
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Bạn được cho một đồ thị với ~n~ đỉnh (được đánh số từ ~1~ đến ~n~) và ~m~ cạnh có hướng và có trọng số. Tìm đường đi có ~k~ cạnh với tổng trọng số nhỏ nhất. Một đường đi có thể đi qua một đỉnh hay cạnh nhiều lần.

Nếu không tồn tại đường đi nào có ~k~ cạnh, in ra IMPOSSIBLE.

Input

Dòng đầu tiên gồm ~3~ số nguyên dương ~n~, ~m~ và ~k~ ~(1 \le n \le 100, 0 \le m \le n \cdot (n-1), 1 \le k \le 10^9)~

~m~ dòng tiếp theo miêu tả các cạnh. Trong đó dòng thứ ~i~ gồm 3 số ~a_i~, ~b_i~ và ~c_i~ ~(1 \le a_i,b_i \le n, a_i \neq b_i, -10^9 \le c_i \le 10^9)~, miêu tả một cạnh có hướng nối từ ~a_i~ đến ~b_i~ với trọng số ~c_i~. Đồ thị trong input đảm bảo không có cạnh trùng hoặc cạnh nối cùng một đỉnh với nhau.

Output

In ra đường đi đi qua ~k~ cạnh với tổng trọng số nhỏ nhất. Nếu không tồn tại đường đi nào đi qua ~k~ cạnh thì in ra IMPOSSIBLE.

Sample 1

Input
3 4 2
1 2 12
2 3 -5
3 1 20
2 1 -1
Output
7

Sample 2

Input
3 4 5
1 2 12
2 3 -5
3 1 20
2 1 -1
Output
17

Sample 3

Input
6 5 3
1 3 -50
2 4 -51
4 3 -52
3 6 -53
4 5 -54
Output
-156

Sample 4

Input
6 5 4
1 3 -50
2 4 -51
4 3 -52
3 6 -53
4 5 -54
Output
IMPOSSIBLE

Note

Hình vẽ dưới đây cho thấy đồ thị trong hai sample đầu tiên. Đường đi tối ưu lần lượt là ~1 \rightarrow 2 \rightarrow 3~ và ~2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.