6075 : 힙+그래프 — MST 프림
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
힙+그래프 — MST 프림 알고리즘
우선순위 큐를 활용하여 최소 신장 트리(MST)를 구성하는 프림(Prim) 알고리즘을 구현하시오.
알고리즘:
1. 임의의 시작 정점을 방문 처리합니다.
2. 방문한 정점에서 연결된 미방문 정점으로의 간선을 힙에 추가합니다.
3. 힙에서 가중치가 가장 작은 간선을 꺼내 미방문 정점이면 MST에 추가합니다.
4. 모든 정점을 방문할 때까지 반복합니다.
그래프가 연결되지 않아 MST를 만들 수 없으면 -1을 출력합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 간선 수 $E$: $1 \le E \le 200{,}000$ (정수)
• 간선 가중치: $1 \le w \le 10^6$ (정수)
우선순위 큐를 활용하여 최소 신장 트리(MST)를 구성하는 프림(Prim) 알고리즘을 구현하시오.
알고리즘:
1. 임의의 시작 정점을 방문 처리합니다.
2. 방문한 정점에서 연결된 미방문 정점으로의 간선을 힙에 추가합니다.
3. 힙에서 가중치가 가장 작은 간선을 꺼내 미방문 정점이면 MST에 추가합니다.
4. 모든 정점을 방문할 때까지 반복합니다.
그래프가 연결되지 않아 MST를 만들 수 없으면 -1을 출력합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 간선 수 $E$: $1 \le E \le 200{,}000$ (정수)
• 간선 가중치: $1 \le w \le 10^6$ (정수)
입력 설명
첫째 줄에 정점 수 N (1 ≤ N ≤ 10,000)과 간선 수 E (1 ≤ E ≤ 100,000)가 주어집니다.
다음 E개의 줄에 간선 정보 u v w가 주어집니다. (무방향, w는 정수 가중치)
다음 E개의 줄에 간선 정보 u v w가 주어집니다. (무방향, w는 정수 가중치)
출력 설명
최소 신장 트리의 간선 가중치 합을 출력합니다. MST가 불가능하면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 7
1 2 4
1 3 1
2 3 2
2 4 5
3 4 8
4 5 2
3 5 10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
10