Roads with a Toll Budget

Difficulty: 1900 5000 ms 128 MB

graphs shortest-paths

Some roads charge tolls; you may pay at most C total tolls. Print the cheapest travel TIME from node 1 to node N within the toll budget, or −1.

Input: the first line has N, M and C; each of the next M lines has u v w t — an undirected road with time w and toll cost t.

Output: the minimum time using at most C total tolls, or −1.

Constraints:

• 2 ≤ N ≤ 10⁴
• 1 ≤ M ≤ 5×10⁴
• 0 ≤ C ≤ 10

Sample Tests

3 3 1
1 2 5 0
2 3 5 1
1 3 20 0

10

2 1 0
1 2 7 0

7

Read the Editorial