Exactly K Flights

Difficulty: 2200 6000 ms 128 MB

graphs matrix-exponentiation

Print the cheapest walk from node 1 to node N using EXACTLY K directed edges (edges may repeat), or −1 if impossible.

Input: the first line has N, M and K; each of the next M lines has u v w.

Output: the minimum cost over walks of exactly K edges, or −1.

Constraints:

• 2 ≤ N ≤ 100
• 1 ≤ K ≤ 10⁹
• 1 ≤ w ≤ 10⁶

Sample Tests

3 3 2
1 2 1
2 3 1
1 3 5

2

2 1 2
1 2 3

-1

Read the Editorial