MathTrauma

문제 링크 : https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 첫 눈에는 까다로워 보이는 문제의 정보 k 개의 선은 공짜, 나머지 중에서 가장 비싼 것을 비용으로 한다. 를 조금 바꿔보자. 우선 공짜 처리되는 k 개는 경로 중 비싼 것들을 차례로 선택함은 당연하다. 비용은 그 다음 비싼 것이 될 것이다. 이 비용을 X 라 하고 주어진 정보를 다르게 쓰면 다음과 같다. 비용이 X (이하)라는 것은 가격이 ..