통신망 구축


답안 제출

Points: 13
시간 제한: 2.0s
메모리 제한: 1G

문제 유형

여러 지역에 통신 서비스를 제공하기 위한 통신망을 구축하려고 한다.

총 \(N\)개의 지역이 있고, 이 중 \(K\)개의 지역에는 이미 통신 기지국이 설치되어 있다. 기지국이 설치된 지역은 케이블을 설치하지 않아도 해당 기지국과 연결된 것으로 본다. 두 지역을 연결하는 통신 케이블을 설치하면, 두 지역은 서로 통신할 수 있다. 여러 개의 케이블을 거쳐 연결된 지역끼리도 서로 통신할 수 있다.

설치할 수 있는 통신 케이블 \(M\)개의 정보와 각 케이블의 설치 비용이 주어진다. 주어진 케이블 중 일부를 설치하여 모든 지역이 적어도 하나의 통신 기지국과 연결되도록 하려고 한다.

모든 지역에 통신 서비스를 제공하기 위해 필요한 최소 케이블 설치 비용을 구하시오.

입력

첫째 줄에 지역의 수 \(N\), 설치할 수 있는 케이블의 수 \(M\), 통신 기지국의 수 \(K\)가 공백으로 구분되어 주어진다.

둘째 줄에 통신 기지국이 설치된 지역의 번호 \(K\)개가 공백으로 구분되어 주어진다.

다음 \(M\)개의 줄에 세 정수 \(u\), \(v\), \(w\)가 공백으로 구분되어 주어진다. 이는 지역 \(u\)와 지역 \(v\)를 연결하는 통신 케이블을 비용 \(w\)로 설치할 수 있다는 뜻이다.

출력

모든 지역이 적어도 하나의 통신 기지국과 연결되도록 케이블을 설치하는 데 필요한 최소 비용을 출력한다.

제한 사항

  • \(2 \le N \le 1,000\)
  • \(N-1 \le M \le \min(100,000, N(N-1)/2)\)
  • \(1 \le K \le N\)
  • \(1 \le u, v \le N\)
  • \(u \ne v\)
  • \(1 \le w \le 1,000,000\)
  • 지역 번호는 \(1\)부터 \(N\)까지이다.
  • 통신 기지국이 설치된 지역의 번호는 모두 서로 다르다.
  • 같은 두 지역을 연결하는 케이블은 최대 하나만 주어진다.
  • 입력으로 주어지는 그래프는 연결 그래프이다.
  • 최소 설치 비용은 \(2,147,483,647\) 이하이다.

예제 입력 1

6 8 2
1 6
1 2 4
2 3 2
3 4 7
4 5 3
5 6 6
2 5 5
1 3 10
4 6 1

예제 출력 1

10

예제 설명 1

다음 네 개의 통신 케이블을 설치할 수 있다.

  • 지역 \(1\)과 지역 \(2\)를 연결하는 비용 \(4\)의 케이블
  • 지역 \(2\)와 지역 \(3\)을 연결하는 비용 \(2\)의 케이블
  • 지역 \(4\)와 지역 \(5\)를 연결하는 비용 \(3\)의 케이블
  • 지역 \(4\)와 지역 \(6\)을 연결하는 비용 \(1\)의 케이블

그러면 지역 \(1\), \(2\), \(3\)은 지역 \(1\)의 통신 기지국과 연결되고, 지역 \(4\), \(5\), \(6\)은 지역 \(6\)의 통신 기지국과 연결된다.

설치 비용의 합은 \(4+2+3+1=10\)이며, 이보다 적은 비용으로 모든 지역을 통신 기지국과 연결할 수 없다.


코멘트

현재 작성된 코멘트가 없습니다.