문제
N개의 정점이 있는 가중치가 양방향 그래프가 주어진다.
N개의 정점 중 K개는 매우 특별하다. 나머지는 평범하다.
정확히 W개의 간선이 특별한 정점과 평범한 정점을 잇는 스패닝 트리 중, 가중치의 합이 최소인 것을 구하여라.
입력
첫 번째 줄에 N, M, K, W가 공백으로 구분되어 주어진다. M은 간선의 개수이다.
다음 줄부터 K줄에 걸쳐 특별한 정점들의 번호가 한 줄에 하나씩 주어진다.
다음 줄부터 M줄에 걸쳐 Ai, Bi, Ci가 공백으로 구분되어 주어진다. Ai와 Bi는 i번째 간선이 잇는 두 정점의 번호, Ci는 i번째 간선의 가중치이다.
- 2 <= N <= 200 000
- 1 <= M <= 500 000
- 1 <= K < N
- 1 <= W < N
- 1 <= Ai, Bi <= N, Ai != Bi
- 1 <= Ci <= 100 000
출력
첫 번째 줄에 조건을 만족하는 스패닝 트리의 가중치의 합의 최솟값을 출력하여라. 만약 조건을 만족하는 스패닝 트리를 만들 수 없다면 -1을 출력하여라.
예제 #1
3 3 1 2
2
1 2 2
1 3 1
2 3 3
5
예제 #2
3 1 1 1
2
1 2 2
-1
출처
NAIPC 2017
로그인해야 코드를 작성할 수 있어요.