반드시 깔아야 하는 광케이블
골드 IV의견: 0
한 통신사가 \(N\)개의 마을을 광케이블로 연결하려 한다. 가능한 케이블 후보는 \(M\)개이며, 후보 \(i\)는 마을 \(u_i\)와 \(v_i\)를 잇고 설치 비용은 \(c_i\)이다.
정부 보조금 조건에 따라, 반드시 설치해야 하는 케이블 후보 \(K\)개가 미리 지정되어 있다. 이 지정된 케이블들은 무조건 설치하고, 나머지 후보 중에서 추가로 골라 모든 마을이 서로 연결되도록 하되, 전체 설치 비용의 합을 최소로 하려 한다.
최소 총 설치 비용을 구하여라. 모든 마을을 연결하는 것이 불가능하거나, 지정된 케이블만으로 이미 사이클이 생겨 조건을 만족할 수 없으면 \(-1\)을 출력한다.
후보 케이블 목록에는 같은 두 마을을 잇는 다중 후보가 있을 수 있고, 자기 루프는 없다.
- \(1 \le N \le 100{,}000\)
- \(1 \le M \le 150{,}000\)
- \(0 \le K \le M\)
- \(1 \le u_i, v_i \le N\), \(u_i \ne v_i\)
- \(1 \le c_i \le 1{,}000{,}000\)
첫째 줄에 \(N\ M\ K\)가 주어진다.
다음 \(M\)개의 줄에 케이블 후보 \(u_i\ v_i\ c_i\)가 \(i = 1, 2, \dots, M\) 순서로 주어진다.
마지막 줄에 반드시 설치해야 하는 케이블 후보의 번호 \(K\)개가 주어진다(번호는 \(1\)부터 시작). \(K = 0\)이면 이 줄은 비어 있다.
최소 총 설치 비용을 한 줄에 출력한다. 불가능하면 \(-1\)을 출력한다.
4 4 1
1 2 1
2 3 2
1 3 5
3 4 1
3
7후보 \(3\)번 \((1,3,5)\)을 반드시 설치. 나머지로 연결하려면 \((1,2,1)\)과 \((3,4,1)\)을 추가해 총 \(5+1+1=7\).
3 3 3
1 2 1
2 3 1
1 3 1
1 2 3
-1지정된 세 케이블이 사이클을 이루므로 조건을 만족할 수 없어 \(-1\).
riseoj 작성
출처 Original
평가 및 의견
반드시 깔아야 하는 광케이블
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
반드시 깔아야 하는 광케이블