시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 3542 | 1585 | 1218 | 42.498% |
채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠다.
공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했다.
채완이는 공사하는 데 드는 비용을 아끼려고 한다.
모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 한다.
위 그림에서 건물과 직선으로 표시된 도로, 해당 도로를 만들 때 드는 비용을 표시해놓은 지도이다.
그림에 있는 도로를 다 설치할 때 드는 비용은 62이다. 모든 건물을 연결하는 도로만 만드는 비용은 27로 절약하는 비용은 35이다.
채완이는 도로가 너무 많아 절약되는 금액을 계산하는 데 어려움을 겪고 있다.
채완이를 대신해 얼마나 절약이 되는지 계산해주자.
첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다.
두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 건물 사이 도로를 만들 때 드는 비용 $c (1 \le c \le 10^6)$가 주어진다. 같은 쌍의 건물을 연결하는 두 도로는 주어지지 않는다.
예산을 얼마나 절약 할 수 있는지 출력한다. 만약 모든 건물이 연결되어 있지 않는다면 -1을 출력한다.
7 9 1 2 15 2 3 7 1 3 3 1 4 8 3 5 6 4 5 4 4 6 12 5 7 1 6 7 6
35
위에서 설명한 것과 같다.
8 10 1 2 4 2 3 9 2 4 9 3 4 4 3 5 1 4 6 14 6 7 5 5 7 3 7 8 7 6 8 3
30
5 4 1 2 1 2 3 1 3 1 1 4 5 5
-1