Internet Installation
Time limit2sMemory limit128 MB
Find the minimum payment for a path from computer 1 to N when up to K of the priciest cables on that path are installed for free.
- Level
Medium7 of 10
- Topics
- Binary search, Shortest path, BFS, Graph
- Solved
- No attempts yet
Problem
Computers are numbered from 1 to N. Initially, no computers are connected, but P candidate cables are given. Each candidate connects two computers and has an installation cost.
Computer 1 is already directly connected to the internet server. Your goal is to make computer N connected to computer 1 through installed cables. It does not matter whether any other computers are connected.
Up to K of the installed cables can be installed for free. For the remaining installed cables, only the most expensive one among them is charged. Determine the minimum amount that must be paid to achieve the goal.
Input
The first line contains the number of computers N(1 ≤ N ≤ 1,000), the number of candidate cables P(1 ≤ P ≤ 10,000), and the number of cables that can be installed for free K(0 ≤ K < N).
Each of the next P lines contains the two computer numbers connected by a cable and that cable's installation cost. Each cost is between 1 and 1,000,000, inclusive.
Output
Print the minimum amount that must be paid to connect computer 1 and computer N. If they cannot be connected, print -1.
Hint
If the path 1-3, 3-2, 2-5 is used, the cable costs are 4, 3, and 9.
Since 1 cable can be installed for free, the cable with cost 9 can be made free. The most expensive remaining cable costs 4, so the paid amount is 4.